On the parameterized complexity of coloring graphs in the absence of a linear forest

Couturier, J.F.; 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}L(u)⊆{1,…,k}. Let PnPn denote the path on n vertices, and G+HG+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. We show that Listk-Coloring is fixed-parameter tractable on graphs with no induced rP1+P2rP1+P2 when parameterized by k+rk+r, and that for any fixed integer r, the problem k-Coloring restricted to such graphs allows a polynomial kernel when parameterized by k. Finally, we show that Listk-Coloring is fixed-parameter tractable on graphs with no induced P1+P3P1+P3 when parameterized by k.

Citation

Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2012). On the parameterized complexity of coloring graphs in the absence of a linear forest. Journal of discrete algorithms, 15, 56-62. https://doi.org/10.1016/j.jda.2012.04.008

• Journal Article Type: Article
• Publication Date: Aug 1, 2012
• Deposit Date: Mar 11, 2013
• Publicly Available Date: Apr 17, 2013
• Journal: Journal of Discrete Algorithms
• Print ISSN: 1570-8667
• Electronic ISSN: 1570-8675
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 15
• Pages: 56-62
• DOI: https://doi.org/10.1016/j.jda.2012.04.008
• Keywords: k-Coloring, Listk-Coloring, H-free, Linear forest, Fixed-parameter tractable.
• Public URL: https://durham-repository.worktribe.com/output/1466804