Polynomial $\chi$-boundedness for excluding $P_5$

Abstract

Resolving a 1985 open problem of Gyárfás, we prove that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path $P_5$. Our approach introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment, which allows us to deduce the desired statement from the Erdős-Hajnal result for $P_5$.

v4: 42 pages plus bibliography and appendices, supersedes arXiv:2504.21127 and arXiv:2510.05724. Incorporated comments from FOCS reviewers