Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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.

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
Keywords:Graph partitioning, Forbidden subgraph, Computational complexity.
Full text:PDF - Accepted Version (219Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/s00453-005-1176-8
Publisher statement:The original publication is available at http://ww.springerlink.com
Record Created:02 Jul 2008
Last Modified:14 Jun 2011 16:40

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library