Hereditary graph classes: when the complexities of coloring and clique cover coincide

Blanché, A.; Dabrowski, K.K.; Johnson, M.; Paulusma, D.

Abstract

graph is (H1;H2)-free for a pair of graphs H1;H2 if it contains no induced subgraph isomorphic to H1 or H2. In 2001, Král’, Kratochvíl, Tuza, and Woeginger initiated a study into the complexity of Colouring for (H1;H2)-free graphs. Since then, others have tried to complete their study, but many cases remain open. We focus on those (H1;H2)-free graphs where H2 is H1, the complement of H1. 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;H)-free graphs for all cases except when H = sP1 + P3 for s 3 or H = sP1 + P4 for s 2. 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 (Pr; Pr)-free graphs.

Citation

Blanché, A., Dabrowski, K., Johnson, M., & Paulusma, D. (2019). Hereditary graph classes: when the complexities of coloring and clique cover coincide. Journal of Graph Theory, 91(3), 267-289. https://doi.org/10.1002/jgt.22431

• Journal Article Type: Article
• Acceptance Date: Oct 29, 2018
• Online Publication Date: Nov 25, 2018
• Publication Date: Jul 31, 2019
• Deposit Date: Nov 1, 2018
• Publicly Available Date: Nov 25, 2019
• Journal: Journal of Graph Theory
• Print ISSN: 0364-9024
• Electronic ISSN: 1097-0118
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 91
• Issue: 3
• Pages: 267-289
• DOI: https://doi.org/10.1002/jgt.22431
• Public URL: https://durham-repository.worktribe.com/output/1314328