Hereditary graph classes: When the complexities of coloring and clique cover coincide. Issue 3 (25th November 2018) - Blanché, Alexandre; Dabrowski, Konrad K.; Johnson, Matthew; Paulusma, Daniël
Abstract: A graph is ( H 1, H 2 ) ‐free for a pair of graphs H 1, H 2 if it contains no induced subgraph isomorphic to H 1 or H 2 . In 2001, Král et al initiated a study into the complexity ofcoloring for ( H 1, H 2 ) ‐free graphs. Since then, others have tried to complete their study, but many cases remain open. We focus on those ( H 1, H 2 ) ‐free graphs where H 2 is H ¯ 1, the complement of H 1 . As these classes are closed under complementation, the computational complexities ofcoloring andclique cover coincide. By combining new and known results, we are able to classify the complexity ofcoloring andclique cover for ( H, H ¯ ) ‐free graphs for all cases except when H = s P 1 + P 3 for s ≥ 3 or H = s P 1 + P 4 for s ≥ 2 . We also classify the complexity ofcoloring on graph classes characterized by forbidding a finite number of self‐complementary induced subgraphs, and we initiate a study of k ‐coloring for ( P r, P ¯ r ) ‐free graphs.