![](/files/happy5.png)
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
![$ \ceil{\frac{\Delta}{2}}+2 $](/files/tex/522a3a86b51cce46cfcff77891e669d1b9ff9147.png)
This conjecture is a special case of Reed's ,
, and
conjecture, which posits that for any graph,
, where
,
, and
are the clique number, maximum degree, and chromatic number of the graph respectively. Reed's conjecture is very easy to prove for complements of triangle-free graphs, but the triangle-free case seems challenging and interesting in its own right.
This conjecture is very much true for large values of ; Johansson proved that triangle-free graphs have chromatic number at most
. Surprisingly, the question appears to be open for every value of
greater than four, up until Johansson's result implies the conjecture.
Kostochka previously proved that the chromatic number of a triangle-free graph is at most , and he proved that for every
there is a
for which a graph of girth
has chromatic number at most
. Specifically, he showed that
is sufficient. In [K] he posed the general problem: "To find the best upper estimate for the chromatic number of the graph in terms of the maximal degree and density or girth."
The conjecture is implied by Brooks' Theorem for . The three smallest open values of
offer natural entry points to this problem. The easiest seems to be:
![$ 6 $](/files/tex/b1111b1328c0de162c7bb7bdbde0496f3f37f563.png)
Perhaps looking at graphs of girth at least five would also be a good starting point.
Bibliography
[K] Kostochka, A. V., Degree, girth and chromatic number. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, pp. 679--696, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, 1978.
*[R] Reed, B.A., , and
, J. Graph Theory 27 (1998) 177-212.
* indicates original appearance(s) of problem.