Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

Updating the complexity status of coloring graphs without a fixed induced linear forest.

Broersma, H.J. and Golovach, P.A. and Paulusma, Daniel and Song, J. (2012) 'Updating the complexity status of coloring graphs without a fixed induced linear forest.', Theoretical computer science., 414 (1). pp. 9-19.

Abstract

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P8-free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P9-free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P8-free graphs. Additionally, we prove that the precoloring extension version of 4-Coloring is NP-complete for P7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P2+P4)-free graphs, a subclass of P7-free graphs. Here P2+P4 denotes the disjoint union of a P2 and a P4. We denote the disjoint union of s copies of a P3 by sP3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.

Item Type:Article
Keywords:Graph coloring, Forbidden induced subgraph, Linear forest.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.tcs.2011.10.005
Record Created:07 Dec 2011 14:35
Last Modified:03 Apr 2013 16:18

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