Skip to main content

Research Repository

Advanced Search

List coloring in the absence of a linear forest

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

Authors

J. F. Couturier

P. A. Golovach

D. Kratsch



Contributors

P. Kolman
Editor

J. Kratochvil
Editor

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.

Citation

Couturier, J. F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2011). List coloring in the absence of a linear forest. In P. Kolman, & J. Kratochvil (Eds.), Graph-theoretic concepts in computer science, 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 ; revised papers (119-130). https://doi.org/10.1007/978-3-642-25870-1_12

Conference Name 37th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2011
Conference Location Tepla Monastery, Czech Republic
Publication Date Jan 1, 2011
Deposit Date Dec 6, 2011
Pages 119-130
Series Title Lecture notes in computer science
Series Number 6986
Series ISSN 0302-9743,1611-3349
Book Title Graph-theoretic concepts in computer science, 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 ; revised papers.
ISBN 9783642258695
DOI https://doi.org/10.1007/978-3-642-25870-1_12
Public URL https://durham-repository.worktribe.com/output/1158308


You might also like



Downloadable Citations