A quasi-polynomial $\chi$-bound for $P_6$-free graphs

Abstract

In this paper we prove that every graph $G$ with no induced six-vertex path satisfies $\chi(G)\le \omega(G)^{c\log_2\omega(G)}$ for $c=45/\log_2(4/3)<109$. The best previous bound was exponential in $\omega(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].