On the chromatic number of triangle-free graphs of large minimum degree (Q1410410)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the chromatic number of triangle-free graphs of large minimum degree |
scientific article; zbMATH DE number 1992715
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the chromatic number of triangle-free graphs of large minimum degree |
scientific article; zbMATH DE number 1992715 |
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
