@inproceedings{7f3e11f5fc8c462cab6bb407790c135a,
title = "Planar graph coloring with forbidden subgraphs : why trees and paths are dangerous",
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.",
author = "H.J. Broersma and F.V. Fomin and J. Kratochvil and G.J. Woeginger",
year = "2002",
doi = "10.1007/3-540-45471-3_17",
language = "English",
isbn = "3-540-43866-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "160--169",
editor = "M. Penttonen and E.M. Schmidt",
booktitle = "Algorithm Theory - SWAT 2002 (Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002)",
address = "Germany",
}