Hereditary graph classes: When the complexities of coloring and clique cover coincide. Issue 3 (25th November 2018)

• Record Type: Journal Article
• Authors: Blanché, Alexandre; Dabrowski, Konrad K.; Johnson, Matthew; Paulusma, Daniël
• Is Part Of: Journal of graph theory. Volume 91:Issue 3(2019)
• Page Start: 267
• Page End: 289
• Publication Date: 2018-11-25
• Subjects: coloring -- hereditary graph class -- self‐complementary; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22431
• Languages: English
• ISSNs: 0364-9024

Abstract

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.