Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path
Alex Scott, Paul D. Seymour, Sophie Spirkl · COMBINATORICA · 2023
Abstract A graphGisH-freeif it has no induced subgraph isomorphic toH. We prove that a $$P_5$$ P5 -free graph with clique number $$\omega \ge 3$$ ω≥3 has chromatic number at most $$\omega ^{\log _2(\omega )}$$ ωlog2(ω) . The best previous result was an exponential upper bound $$(5/27)3^{\omega }$$ (5/27)3ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for $$P_5$$ P5 , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for $$P_5$$ P5 -free graphs, and our result is an attempt to approach that.