New graph coloring bound found with AI help
Coloring graphs with no long induced path
For anyone working on graph theory or algorithmic problems, this is a concrete improvement in a fundamental area of mathematics.
Researchers improved a mathematical theorem about graph coloring by using AI. They proved that for graphs without long induced paths, the number of colors needed is limited by a new formula. The proof combined two existing arguments and was assisted by Claude Fable 5.1 and GPT Pro.
Coloring graphs with no long induced path
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 found with the assistance of Claude Fable 5.1 of Anthropic and GPT Pro of OpenAI.
