INDUCED SUBGRAPHS OF GRAPHS WITH LARGE CHROMATIC NUMBER. III. LONG HOLES

摘要

We prove a 1985 conjecture of Gyarfas that for all k, a"", every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than a"".