Partitions of graphs into cographs

DOI10.1016/J.DISC.2010.07.011MaRDI QIDQ607000zbMATH OpenOpenAlexWikidataFDO

Authors J. Nešetřil, John Gimbel

Publication date 19 November 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2010.07.011

zbMATH Keywords

graph coloringcograph\(P_4\)-free coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Vertex partitions of graphs into cographs and stars
• Vertex arboricity of cographs
• Partitioning graphs into complete and empty graphs
• Partitioning cographs into cliques and stable sets
• On cocolourings and cochromatic numbers of graphs

Cites work

• scientific article; zbMATH DE number 3910413 (Why is no real title available?)
• scientific article; zbMATH DE number 3912409 (Why is no real title available?)
• scientific article; zbMATH DE number 4010539 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 1151379 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 867706 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• A short proof of the existence of highly chromatic hypergraphs without short cycles
• Chromatically optimal rigid graphs
• Coloring graphs with fixed genus and girth
• Colorings and girth of oriented planar graphs
• Complement reducible graphs
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Gadget classification
• On Injective Colourings of Chordal Graphs
• On \(P_4\)-transversals of chordal graphs
• On a property of the class of n-colorable graphs
• On chromatic number of finite set-systems
• On cocolourings and cochromatic numbers of graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Some extremal results in cochromatic and dichromatic theory
• Some simplified NP-complete graph problems
• The complexity of \(G\)-free colourability
• The subchromatic number of a graph

Cited in

(14)

• Dynamic \(F\)-free coloring of graphs
• On the computational complexity of the bipartizing matching problem
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• Partitions of Graphs
• Transducing paths in graph classes with unbounded shrubdepth
• Vertex partitions of graphs into cographs and stars
• Excluding pairs of graphs
• On the construction of cograph color critical graphs
• Representing graphs as the intersection of cographs and threshold graphs
• Note on strong product graph dimension
• Co-2-plex vertex partitions
• Partitioning cographs into cliques and stable sets
• Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
• Colorings of oriented planar graphs avoiding a monochromatic subgraph

This page was built for publication: Partitions of graphs into cographs

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