Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Blanché, A. and Dabrowski, K.K. and Johnson, M. and Paulusma, D. (2019) 'Hereditary graph classes : when the complexities of coloring and clique cover coincide.', Journal of graph theory., 91 (3). pp. 267-289.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(517Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1002/jgt.22431
Publisher 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.
Date accepted:29 October 2018
Date deposited:02 November 2018
Date of first online publication:25 November 2018
Date first made open access:25 November 2019

Save or Share this output

Export:
Export
Look up in GoogleScholar