Coloring graphs without short cycles and long induced paths

Golovach, P.A.; Paulusma, D.; Song, J.

Abstract

For an integer k≥1, a graph G is k-colorable if there exists a mapping c:VG→{1,…,k} such that c(u)≠c(v) whenever u and v are two adjacent vertices. For a fixed integer k≥1, the k-Coloring problem is that of testing whether a given graph is k-colorable. The girth of a graph G is the length of a shortest cycle in G. For any fixed g≥4 we determine a lower bound ℓ(g), such that every graph with girth at least g and with no induced path on ℓ(g) vertices is 3-colorable. We also show that for all fixed integers k,ℓ≥1, thek-Coloring problem can be solved in polynomial time for graphs with no induced cycle on four vertices and no induced path on ℓ vertices. As a consequence, for all fixed integers k,ℓ≥1 and g≥5, the k-Coloring problem can be solved in polynomial time for graphs with girth at least g and with no induced path on ℓ vertices. This result is best possible, as we prove the existence of an integer ℓ∗, such that already 4-Coloring is NP-complete for graphs with girth 4 and with no induced path on ℓ∗ vertices.

Citation

Golovach, P., Paulusma, D., & Song, J. (2014). Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics, 167, 107-120. https://doi.org/10.1016/j.dam.2013.12.008

• Journal Article Type: Article
• Publication Date: Apr 1, 2014
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 6, 2015
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 167
• Pages: 107-120
• DOI: https://doi.org/10.1016/j.dam.2013.12.008
• Keywords: Graph coloring, Girth, Forbidden induced subgraph
• Public URL: https://durham-repository.worktribe.com/output/1417545