Coloring graphs without short cycles and long induced paths

For an integer k≥1k≥1, a graph GG is kk-colorable if there exists a mapping c:VG→{1,…,k}c:VG→{1,…,k} such that c(u)≠c(v)c(u)≠c(v) whenever uu and vv are two adjacent vertices. For a fixed integer k≥1k≥1, the kk-Coloring problem is that of testing whether a given graph is kk-colorable. The girth of a graph GG is the length of a shortest cycle in GG. For any fixed g≥4g≥4 we determine a lower bound ℓ(g)ℓ(g), such that every graph with girth at least gg and with no induced path on ℓ(g)ℓ(g) vertices is 3-colorable. We also show that for all fixed integers k,ℓ≥1k,ℓ≥1, thekk-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,ℓ≥1k,ℓ≥1 and g≥5g≥5, the kk-Coloring problem can be solved in polynomial time for graphs with girth at least gg 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.