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:

List coloring in the absence of a linear forest.

Couturier, J.F. and Golovach, P.A. and Kratsch, D. and Paulusma, Daniel (2011) 'List coloring in the absence of a linear forest.', in Graph-theoretic concepts in computer science, 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 ; revised papers. Berlin: Springer, pp. 119-130. Lecture notes in computer science. (6986).

Abstract

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k -Coloring problem requires in addition that every vertex u must receive a color from some given set L(u) ⊆ {1,…,k}. Let P n denote the path on n vertices, and G + H and rH the disjoint union of two graphs G and H and r copies of H, respectively. For any two fixed integers k and r, we show that List k -Coloring can be solved in polynomial time for graphs with no induced rP 1 + P 5, hereby extending the result of Hoàng, Kamiński, Lozin, Sawada and Shu for graphs with no induced P 5. Our result is tight; we prove that for any graph H that is a supergraph of P 1 + P 5 with at least 5 edges, already List 5-Coloring is NP-complete for graphs with no induced H. We also show that List k -Coloring is fixed parameter tractable in k + r on graphs with no induced rP 1 + P 2, and that k-Coloring restricted to such graphs allows a polynomial kernel when parameterized by k. Finally, we show that List k -Coloring is fixed parameter tractable in k for graphs with no induced P 1 + P 3.

Item Type:Book chapter
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1007/978-3-642-25870-1_12
Record Created:13 Dec 2011 14:20
Last Modified:03 Apr 2013 16:23

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