Skip to main content

Research Repository

Advanced Search

Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult

Broersma, H.J.; Fomin, F.V.; Kratochvil, J.; Woeginger, G.J.

Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult Thumbnail


Authors

H.J. Broersma

F.V. Fomin

J. Kratochvil

G.J. Woeginger



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.

Citation

Broersma, H., Fomin, F., Kratochvil, J., & Woeginger, G. (2006). Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult. Algorithmica, 44(4), 343-361. https://doi.org/10.1007/s00453-005-1176-8

Journal Article Type Article
Publication Date 2006-05
Deposit Date Jul 2, 2008
Publicly Available Date Mar 29, 2024
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 44
Issue 4
Pages 343-361
DOI https://doi.org/10.1007/s00453-005-1176-8
Keywords Graph partitioning, Forbidden subgraph, Computational complexity.

Files




You might also like



Downloadable Citations