# Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult

Broersma, H.J.
and
Fomin, F.V.
and
Kratochvil, J.
and
Woeginger, G.J.
(2006)
*Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult.*
Algorithmica, 44
(4).
pp. 343-361.
ISSN 0178-4617

PDF
Restricted to UT campus only : Request a copy 241kB |

Abstract: | We consider the problem of coloring a planar graph with the minimum number of colors so 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 noninduced) 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 with at least one edge, and it is polynomially solvable in all other cases. We also derive results for several forbidden sets of cycles. In particular, we prove that it is NP-complete to decide if a planar graph can be 2-colored so that no cycle of length at most 5 is monochromatic. |

Item Type: | Article |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/63664 |

Official URL: | http://dx.doi.org/10.1007/s00453-005-1176-8 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 228211