Improved coloring limits for graphs without long induced paths
Coloring graphs with no long induced path
Discrete Mathematics
Summary
This paper studies how to color certain graphs that don't have long paths inside them. Coloring a graph means assigning colors to points so that no connected points share a color. The authors improved previous upper limits on how many colors are needed depending on the size of the largest complete subgraph and the length of forbidden paths. They use a new mathematical approach to refine earlier arguments and get tighter bounds.
What this means in practice
- •For software engineers: Design coloring algorithms that handle graphs without long induced paths more efficiently thanks to tighter theoretical color limits.
- •For network designers: Use improved coloring bounds to optimize resource assignments in networks structured with constraints excluding long induced paths.
A theory result. No direct application yet.
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.