On the chromatic number of triangle-free graphs of large minimum degree (Q1410410)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the chromatic number of triangle-free graphs of large minimum degree |
scientific article |
Statements
On the chromatic number of triangle-free graphs of large minimum degree (English)
0 references
14 October 2003
0 references
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\).
0 references
triangle-free graphs
0 references
chromatic number
0 references
