Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and paths make things difficult
Hajo J. Broersma, Fedor V. Fomin, Jan Kratochvı́l, Gerhard J. Woeginger · 2003
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...