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. and Golovach, P.A. and Kratsch, D. and Paulusma, Daniel (2015) 'List coloring in the absence of a linear forest.', Algorithmica., 71 (1). pp. 21-35.


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 Listk-Coloring problem requires in addition that every vertex u must receive a color from some given set L(u)⊆{1,…,k}. Let Pn 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 Listk-Coloring can be solved in polynomial time for graphs with no induced rP1+P5, hereby extending the result of Hoàng, Kamiński, Lozin, Sawada and Shu for graphs with no induced P5. Our result is tight; we prove that for any graph H that is a supergraph of P1+P5 with at least 5 edges, already List 5-Coloring is NP-complete for graphs with no induced H.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:30 March 2013
Date deposited:17 April 2013
Date of first online publication:06 April 2013
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar