Polynomial 𝜒-boundedness for excluding the five-vertex path
Polynomial 𝜒-boundedness for excluding the five-vertex path
-
Tung Nguyen, Oxford
Fine Hall 224
We overview the recent resolution of a 1985 open problem of Gyárfás, that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path. The proof 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 the five-vertex path.