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: | |
| Look up in GoogleScholar |
