Coloring graphs characterized by a forbidden subgraph ?
The Coloring problem is to test whether a given graph can be colored with at most k k colors for some given k k , such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H H as an induced subgraph is known for each fixed graph H H . A natural variant is to forbid a graph H H only as a subgraph. We call such graphs strongly H H -free and initiate a complexity classification of Coloring for strongly H H -free graphs. We show that Coloring is NP-complete for strongly H H -free graphs, even for k=3 k = 3 , when H H contains a cycle, has maximum degree at least5, or contains a connected component with two vertices of degree4. We also give three conditions on a forest H H of maximum degree at most4 and with at most one vertex of degree4 in each of its connected components, such that Coloring is NP-complete for strongly H H -free graphs even for k=3 k = 3 . Finally, we classify the computational complexity of Coloring on strongly H H -free graphs for all fixed graphs H H up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when H H is a forest that has at most seven vertices and maximum degree at most4.
forbidden subgraphs complexity algorithms graph coloring