List Coloring in the Absence of a Linear Forest

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

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