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.
[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