Résumé en anglais

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