List Coloring in the Absence of a Linear Forest

Couturier, J.; Golovach, P.A.; Kratsch, D.; Paulusma, D.

doi:10.1007/s00453-013-9777-0

List Coloring in the Absence of a Linear Forest

Couturier, J.; Golovach, P.A.; Kratsch, D.; Paulusma, D.

Authors

J. Couturier

P.A. Golovach

D. Kratsch

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

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 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.

Citation

Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2015). List Coloring in the Absence of a Linear Forest. Algorithmica, 71(1), 21-35. https://doi.org/10.1007/s00453-013-9777-0

Journal Article Type	Article
Acceptance Date	Mar 30, 2013
Online Publication Date	Apr 6, 2013
Publication Date	Jan 1, 2015
Deposit Date	Apr 15, 2013
Publicly Available Date	Apr 17, 2013
Journal	Algorithmica
Print ISSN	0178-4617
Electronic ISSN	1432-0541
Publisher	Springer
Peer Reviewed	Peer Reviewed
Volume	71
Issue	1
Pages	21-35
DOI	https://doi.org/10.1007/s00453-013-9777-0
Public URL	https://durham-repository.worktribe.com/output/1487502