@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",

}