{"id":"arxiv/2609.08847","url":"https://arxiv.org/abs/2609.08847","tags":["math.CO","cs.DM"],"score":0,"title":"Coloring graphs with no long induced path","domain":"math.CO","source":"arxiv","authors":["Sang-il Oum"],"reviews":0,"subject":"math.CO","summary":"Let $P_t$ denote the induced path on $t$ vertices. Let $ω(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 $χ(G)\\le(t-1)^{ω(G)-1}$, and Gravier, Hoàng, and Maffray (2003) improved this to $χ(G)\\le (t-2)^{ω(G)-1}$ for $t\\ge4$. We lower the base of the exponential by one: for every $t\\ge5$, 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}