Coloring graphs with no long induced path

Abstract

Let $P_t$ denote the induced path on $t$ vertices. Let $\omega (G)$ denote the maximum number of vertices in a clique of a graph $G$. Gyárfás (1987) proved that every $P_t$-free graph $G$ satisfies $\chi (G)\le (t-1{)}^{\omega (G)-1}$, and Gravier, Hoàng, and Maffray (2003) improved this to $\chi (G)\le (t-2{)}^{\omega (G)-1}$ for $t\ge 4$. We lower the base of the exponential by one: for every $t\ge 5$, every $P_t$-free graph $G$ satisfies \[ χ(G)\le 3\,(t-3)^{ω(G)+4}. \] The proof combines two refinements of the Gyárfás path argument and was developed with the assistance of Claude Fable 5.1 of Anthropic and GPT Pro of OpenAI.

arXiv comment8 pages; the bound is improved; Added references and clarified attribution of the proof methods