Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path

Abstract

A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph with clique number $\omega \ge 3$ has chromatic number at most ${\omega }^{{\log }_2(\omega )}$. The best previous result was an exponential upper bound $(5/27)3^{\omega }$, due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdos-Hajnal conjecture holds for $P_5$, which is the smallest open case. Thus there is great interest in whether there is a polynomial bound for $P_5$-free graphs, and our result is an attempt to approach that.