{"id":"arxiv/2610.33407","url":"https://arxiv.org/abs/2610.33407","tags":["math.CO"],"score":0,"title":"A quasi-polynomial $χ$-bound for $P_6$-free graphs","domain":"math.CO","source":"arxiv","authors":["Shenwei Huang","Yidong Zhou","Yuwen Zhou"],"reviews":0,"subject":"math.CO","summary":"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].","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-24","reactions":{}}