Paperlane

no. 3 · Tuesday 27 October 2026

A quasi-polynomial $χ$-bound for $P_6$-free graphs

Shenwei Huang, Yidong Zhou and Yuwen Zhou

math.CO · 16 pp

Abstract

In this paper we prove that every graph $G$ with no induced six-vertex path satisfies $χ(G)\le ω(G)^{c\log_2ω(G)}$ for $c=45/\log_2(4/3)<109$. The best previous bound was exponential in $ω(G)$. Our result is the first quasi-polynomial bound for $P_6$-free graphs and generalizes the bound for $P_5$-free graphs by Scott, Seymour, and Spirkl [Polynomial bounds for chromatic number. {IV}. {A} near-polynomial bound for excluding the five-vertex path. {\em Combinatorica}, 43(5):845–852, 2023].

comments
16 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.33407 ↗