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

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

doi:10.1002/jgt.22431

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

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

Authors

A. Blanché

K.K. Dabrowski

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

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

Files

Accepted Journal Article (529 Kb)
PDF

Copyright Statement
This is the peer reviewed version of the following article: Blanché, A., Dabrowski, K.K., Johnson, M. & Paulusma, D. (2018). Hereditary graph classes: when the complexities of coloring and clique cover coincide. Journal of Graph Theory, which has been published in final form at https://doi.org/10.1002/jgt.22431. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.