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

DOI10.1002/JGT.22431zbMATH Open1417.05060OpenAlexW2963798790MaRDI QIDQ5229535FDOQ5229535

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

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

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) Structural characterization of families of graphs (05C75)

Abstract: A graph is $(H_1,H_2)$-free for a pair of graphs $H_1,H_2$ if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. In 2001, Kr'al', Kratochv'{i}l, Tuza, and Woeginger initiated a study into the complexity of Colouring for $(H_1,H_2)$-free graphs. Since then, others have tried to complete their study, but many cases remain open. We focus on those $(H_1,H_2)$-free graphs where $H_2$ is $overline{H}_1$, the complement of $H_1$. As these classes are closed under complementation, the computational complexities of Colouring and Clique Cover coincide. By combining new and known results, we are able to classify the complexity of Colouring and Clique Cover for $(H,overlineH)$-free graphs for all cases except when $H=s{P}_1+P_3$ for $sgeq3$ or $H=s{P}_1+P_4$ for $sgeq2$. We also classify the complexity of Colouring on graph classes characterized by forbidding a finite number of self-complementary induced subgraphs, and we initiate a study of $k$-Colouring for $(P_r,overline{P}_r)$-free graphs.

Recommendations

• Complexity of \(C_K\)-coloring in hereditary classes of graphs
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• scientific article; zbMATH DE number 468640
• scientific article; zbMATH DE number 1979486
• On the structure of hereditary classes of graphs
• Some new hereditary classes where graph coloring remains NP-hard
• Hereditary classes of graphs: a parametric approach
• On the size of hereditary classes of graphs
• Clique-width for hereditary graph classes
• On hereditary Helly classes of graphs

Cited in

(10)

• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• scientific article; zbMATH DE number 1286302 (Why is no real title available?)
• Clique-width for graph classes closed under complementation
• scientific article; zbMATH DE number 7651174 (Why is no real title available?)
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Colouring square-free graphs without long induced paths
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• Some new hereditary classes where graph coloring remains NP-hard
• scientific article; zbMATH DE number 7204407 (Why is no real title available?)

This page was built for publication: Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide

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