×

On the chromatic number of triangle-free graphs of large minimum degree. (English) Zbl 1026.05042

It is proved that, for each real number \(c>1/3\), the triangle-free graphs with minimum degree at least \(cn\) (\(n\) the number of vertices) have bounded chromatic number. This settles a longstanding open problem of Erdős and Simonovits who showed that there is no such result for \(c<1/3\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI Link