Publication at Faculty of Mathematics and Physics |
2006
Abstract
We provide a detailed study of the computational complexity of the problem of coloring a planar graph with the minimum number of colors so that each color class avoids a forbidden graph as a subgraph. We show that the 2-coloring problem is NP-hard if the forbidden graph is a tree with at least two edges, and polynomially solvable otherwise, and the 3-coloring problem is NP-hard if the forbidden graph is a path with at least one edge, and polynomially solvable otherwise.