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

Source 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].