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

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

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

Publication date: 15 August 2019

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

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.

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

Recommendations

• scientific article; zbMATH DE number 7525468
• 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

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)

Cited In (10)

• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• Title not available (Why is that?)
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• Clique-Width for Graph Classes Closed under Complementation
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the chromatic number of (\(P_6\), diamond)-free graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Colouring square-free graphs without long induced paths
• Some new hereditary classes where graph coloring remains NP-hard

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)