Coloring Graphs Characterized by a Forbidden Subgraph

The

Coloring

problem is to test whether a given graph can be colored with at most

k

colors for some given

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

as an induced subgraph is known for each fixed graph

H

. A natural variant is to forbid a graph

H

only as a subgraph. We call such graphs strongly

H

-free and initiate a complexity classification of

Coloring

for strongly

H

-free graphs. We show that

Coloring

is

NP

-complete for strongly

H

-free graphs, even for

k

 = 3, when

H

contains a cycle, has maximum degree at least five, or contains a connected component with two vertices of degree four. We also give three conditions on a forest

H

of maximum degree at most four and with at most one vertex of degree four in each of its connected components, such that

Coloring

is

NP

-complete for strongly

H

-free graphs even for

k

 = 3. Finally, we classify the computational complexity of

Coloring

on strongly

H

-free graphs for all fixed graphs

H

up to seven vertices. In particular, we show that

Coloring

is polynomial-time solvable when

H

is a forest that has at most seven vertices and maximum degree at most four.