On the structure of triangle-free graphs of large minimum degree (Q858147)

For all \(\varepsilon, N > 0\) Hajnal constructed triangle-free graphs \(G\) on \(n\) vertices of minimum degree at least \((1/3-\varepsilon)n\) and chromatic number at least \(N\). \textit{C. Thomassen} [Combinatorica 22, No. 4, 591--596 (2002; Zbl 1026.05042)] proved that this result is sharp: for every \(\varepsilon > 0\) there exists \(K=K(\varepsilon)\) such that the chromatic number of every triangle-free graph of minimum degree at least \((1/3+\varepsilon)n\) has chromatic number at most \(K(\varepsilon)\). The author improves this result in the following sense: for every \(\varepsilon > 0\) there exists \(L=L(\varepsilon)\) such that every triangle-free graph of minimum degree at least \((1/3+\varepsilon)n\) is homomorphic to a triangle-free graph on at most \(L\) vertices. The proof is based on the Szemerédi regularity lemma.