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.
기초과학연구원 이산수학그룹