**Originator(s):** P. Erdös and M. Simonovits, modified by
S. Brandt and others

**Conjecture/Question:**
If *G* is an *n*-vertex triangle-free graph whose minimum degree
exceeds *n*/3, then *G* is 4-colorable.

**Definitions/Background/motivation:**
Triangle-free graphs may have arbitrarily large chromatic number, but
known constructions of triangle-free graphs with large chromatic number
have vertices of relatively small degree. For every positive constant
*\epsilon*, Erdös and Simomovits [ES] (attributed to Hajnal?)
constructed graphs with arbitrarily large chromatic number and minimum degree
within a factor *1-\epsilon* of *n*/3. They conjectured
that minimum degree exceeding *n/3* would force 3-colorability.
(The existence of such a threshold is motivated by the result of
Andrásfai-Erdös-Sós [AES] showing that triangle-free graphs
with minimum degree exceeding (2/5)*n* are bipartite.)

Häggkvist [H] found a counterexample, based on a weighted vertex expansion
of the Grötzsch graph; expanding each vertex into an independent set.
The chromatic number remains 4, but the vertex degrees are averaged so that
the minimum degree of the resulting *n*-vertex graph is (10/29)*n*.
Häggkvist conjectured that the minimum degree could not exceed
(10/29)*n* in a triangle-free graph that is not 3-colorable, and Jin [J]
proved this.

Jin conjectured that the chromatic number could still be arbitrarily large when
the minimum degree exceeds (1/3)*n*. Brandt [B1] conjectured on the other
hand that such graphs are all 4-colorable, and in [B2] he proved this for
maximal triangle-free graphs that are regular. Thomassen proved that for
*c >1/3* the chromatic number of every triangle-free graph with minimum
degree exceeding *cn* is bounding by a constant the depends on ,
and Luczak improved this using the Regularity Lemma.
More history about the problem appears in Brandt [B1].

**SOLUTION:**
Brandt and Thomassé [BT] announced that triangle-free *n*-vertex
graphs with minimum degree exceeding *n*/3 are 4-colorable. The proof was
found in 2004, but the paper was not yet published as of April 2007. The
result was reported at an Oberwolfach conference in January of 2005.

**References:**

[AES] Andrásfai, B.; Erdös, P.; Sós, V. T.
On the connection between chromatic number, maximal clique and minimal degree
of a graph. Discrete Math. 8 (1974), 205--218.

[B1] Brandt, Stephan On the structure of dense triangle-free graphs. Combin.
Probab. Comput. 8 (1999), no. 3, 237--245.

[B2] Brandt, Stephan A 4-colour problem for dense triangle-free graphs. Cycles
and colourings (Stará Lesná, 1999). Discrete Math. 251 (2002),
no. 1-3, 33--46.

[BT] Brandt, Stephan; Thomassé, St\eacute;phan
Dense triangle-free graphs are four-colourable: A solution to the
Erdös-Simonovits problem.

[ES] Erdös, P.; Simonovits, M. On a valence problem in extremal graph
theory. Discrete Math. 5 (1973), 323--334.

[H] Häggkvist, Roland Odd cycles of specified length in nonbipartite
graphs. Graph theory (Cambridge, 1981), pp. 89--99, North-Holland Math. Stud.,
62, North-Holland, Amsterdam-New York, 1982.

[J] Jin, Guo Ping Triangle-free four-chromatic graphs. Discrete Math. 145
(1995), no. 1-3, 151--170.

**Keywords: chromatic number, triangle-free, minimum degree**