Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide

DOI10.1002/jgt.22431zbMath1417.05060arXiv1607.06757OpenAlexW2963798790MaRDI QIDQ5229535

Alexandre Blanché, Konrad K. Dabrowski, Daniël Paulusma, Matthew Johnson

Publication date: 15 August 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.06757

zbMATH Keywords

coloringhereditary graph classself-complementary subgraph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable, On the chromatic number of (\(P_6\), diamond)-free graphs, Clique-Width for Graph Classes Closed under Complementation, Unnamed Item, Colouring square-free graphs without long induced paths