Hereditary graph classes: When the complexities of coloring and clique cover coincide
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma · Journal of Graph Theory · 2018
Abstract A graph is ‐free for a pair of graphs if it contains no induced subgraph isomorphic to or . In 2001, Král et al initiated a study into the complexity of coloring for ‐free graphs. Since then, others have tried to complete their study, but many cases remain open. We focus on those ‐free graphs where is , the complement of . As these classes are closed under complementation, the computational complexities of coloring and clique cover coincide. By combining new and known results, we are able to classify the complexity of coloring and clique cover for ‐free graphs for all cases except when for or for . We also classify the complexity of coloring on graph classes characterized by forbidding a finite number of self‐complementary induced subgraphs, and we initiate a study of ‐ coloring for ‐free graphs.