Premium
Hereditary graph classes: When the complexities of coloring and clique cover coincide
Author(s) -
Blanché Alexandre,
Dabrowski Konrad K.,
Johnson Matthew,
Paulusma Daniël
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22431
Subject(s) - combinatorics , mathematics , split graph , cograph , graph coloring , chordal graph , graph , complete coloring , discrete mathematics , edge coloring , 1 planar graph , line graph , graph power
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 of coloring 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 isH ¯ 1 , the complement of H 1 . 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 ( 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 of coloring 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.