ALCOMFT-TR-02-15

Hajo Broersma, Fedor. V Fomin, Jan Kratochv\'\il and Gerhard J. Woeginger
Planar graph coloring with forbidden subgraphs: Why trees and paths are dangerous.
Paderborn. Work package 4. May 2002.

Abstract: 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.

Postscript file: ALCOMFT-TR-02-15.ps.gz (94 kb).