Home » Subject » Graph Theory » Coloring » Vertex coloring
Importance: Medium ✭✭
Author(s): Kostochka, Alexandr V.
Reed, Bruce A.
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: chromatic number
girth
maximum degree
triangle free
Recomm. for undergrads: no
Posted by: Andrew King
on: April 17th, 2009
Conjecture   A triangle-free graph with maximum degree $ \Delta $ has chromatic number at most $ \ceil{\frac{\Delta}{2}}+2 $.

This conjecture is a special case of Reed's $ \omega $, $ \Delta $, and $ \chi $ conjecture, which posits that for any graph, $ \chi \leq \lceil\frac 12(\Delta+1+\omega)\rceil $, where $ \omega $, $ \Delta $, and $ \chi $ 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 $ \Delta $; Johansson proved that triangle-free graphs have chromatic number at most $ \frac{9\Delta}{\ln \Delta} $. Surprisingly, the question appears to be open for every value of $ \Delta $ 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 $ \frac{2\Delta}{3}+2 $, and he proved that for every $ \Delta \geq 5 $ there is a $ g $ for which a graph of girth $ g $ has chromatic number at most $ \frac{\Delta}2+2 $. Specifically, he showed that $ g \geq 4(\Delta+2)\ln \Delta $ 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 $ \Delta\leq 5 $. The three smallest open values of $ \Delta $ offer natural entry points to this problem. The easiest seems to be:

Problem   Does there exist a $ 6 $-chromatic triangle-free graph of maximum degree 6?

Perhaps looking at graphs of girth at least five would also be a good starting point.

Related problems

Reed's omega, delta, and chi conjecture
Grunbaum's Conjecture

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., $ \omega, \Delta $, and $ \chi $, J. Graph Theory 27 (1998) 177-212.


* indicates original appearance(s) of problem.
1 comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options