We consider the problem of coloring a planar graph with the minimum number of colors such that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem.
We present a complete picture for the case with a single forbidden connected (induced or non-induced) subgraph. The 2-coloring problem is NP-hard if the forbidden subgraph is a tree with at least two edges, and it is polynomially solvable in all other cases. The 3-coloring problem is NP-hard if the forbidden subgraph is a path, and it is polynomially solvable in all other cases. We also derive results for several forbidden sets of cycles.
|Title of host publication||Algorithm Theory - SWAT 2002 (Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002)|
|Editors||M. Penttonen, E.M. Schmidt|
|Place of Publication||Berlin|
|Publication status||Published - 2002|
|Name||Lecture Notes in Computer Science|