We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details

Blanché, A., Dabrowski, K.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.

Author(s) from Durham


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.