Partitioning extended P₄-laden graphs into cliques and stable sets

DOI10.1016/J.IPL.2012.07.011MaRDI QIDQ456142zbMATHOpenAlexFDO

Authors Raquel S. F. Bravo, Sulamita Klein, Fábio Protti, Loana T. Nogueira, Rudini M. Sampaio

Publication date 23 October 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2012.07.011

zbMATH Keywords

graph partitiongraph algorithmscliques\((k\(P_{4}\)-laden graphs\ell )\)-cocoloring\ell )\)-graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Fixed-parameter algorithms for the cocoloring problem
• Two fixed-parameter algorithms for the cocoloring problem
• Partitioning cographs into cliques and stable sets
• On cocolourings and cochromatic numbers of graphs
• Partitions of graphs into cographs

Cites work

• scientific article; zbMATH DE number 434912 (Why is no real title available?)
• scientific article; zbMATH DE number 3903967 (Why is no real title available?)
• scientific article; zbMATH DE number 3611388 (Why is no real title available?)
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Characterizing –partitionable Cographs
• Chromatic number versus chromatic number in graphs with bounded clique number
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
• Generalized colouring (matrix partitions) of cographs
• Matrix partitions of perfect graphs
• On split-coloring problems
• On the \(b\)-coloring of \(P_{4}\)-tidy graphs
• Partitioning chordal graphs into independent sets and cliques
• Partitioning cographs into cliques and stable sets
• Some extremal results in cochromatic and dichromatic theory
• The complexity of some problems related to GRAPH 3-COLORABILITY
• \(P_{4}\)-laden graphs: A new class of brittle graphs

Cited in

(8)

• Clique cycle transversals in graphs with few \(P_{4}\)'s
• Two fixed-parameter algorithms for the cocoloring problem
• PSPACE-completeness of two graph coloring games
• Partitioning a graph into disjoint cliques and a triangle-free graph
• PSPACE-hardness of two graph coloring games
• Fixed-parameter algorithms for the cocoloring problem
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Perfect matching cuts partitioning a graph into complementary subgraphs

This page was built for publication: Partitioning extended \(P_4\)-laden graphs into cliques and stable sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456142)