Improved color limits found for graphs without long induced paths
Coloring graphs with no long induced path
Discrete Mathematics
Summary
Coloring a graph means assigning colors to points so that connected ones don’t share the same color. The problem gets harder when the graph avoids long chains of points linked in a row, called induced paths. Earlier work gave formulas to estimate the maximum colors needed based on the size of the biggest fully connected group in the graph. The authors improved these estimates for graphs without long induced paths, giving tighter bounds that grow more slowly. They did this by refining a known method used for analyzing paths in graphs.
graph coloringinduced pathcliquechromatic numberP_t-free graphGyárfás path argumentcombinatoricsgraph theory
Authors
Sang-il Oum
Abstract
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$. Previously 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 prove that for $t\ge5$,every $P_t$-free graph $G$ satisfies $χ(G)<c_tλ_t^{ω(G)-1}$, where $λ_t=\tfrac12\bigl(t-2+\sqrt{t(t-4)}\bigr)<t-2$ and $c_t=\sqrt{1+4/(t(t-4))}=1+O(t^{-2})$ as $t\to\infty$. The proof is based on a refinement of the Gyárfás path argument and was found by Claude Fable 5.1 of Anthropic.