PreprintarXiv licencearXiv
Coloring graphs with no long induced path
Abstract
Let Pt 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 Pt-free graph G satisfies χ(G)≤(t−1)ω(G)−1, and Gravier, Hoàng, and Maffray (2003) improved this to χ(G)≤ (t−2)ω(G)−1 for t≥4. We lower the base of the exponential by one: for every t≥5, every Pt-free graph G satisfies χ(G)≤ 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.
Related
- Hull Games of Induced Path Convexities in Graphs
- Long induced cycles in pseudorandom graphs
- Bounds for B-coloring planar and outerplanar graphs
- COLORING SEMIMINIMAL CAYLEY GRAPHS
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
BibTeX
@misc{oum2026coloring,
title = {{Coloring graphs with no long induced path}},
author = {Sang-il Oum},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08847},
eprint = {2609.08847},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08847},
}
RIS
TY - UNPB
TI - Coloring graphs with no long induced path
AU - Sang-il Oum
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.08847
UR - https://arxiv.org/abs/2609.08847
AB - 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)≤(t−1)^ω(G)−1, and Gravier, Hoàng, and Maffray (2003) improved this to χ(G)≤ (t−2)^ω(G)−1 for t≥4. We lower the base of the exponential by one: for every t≥5, every P_t-free graph G satisfies χ(G)≤ 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.
ER -