Home » Subject » Graph Theory » Coloring » Vertex coloring

Bounding the chromatic number of triangle-free graphs with fixed maximum degree

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.
add new comment

Modifying the conjecture

On May 16th, 2020 Anonymous says:

From Reed's conjecture, it seems that the ceiling has to be replaced by flooring. Thanks.

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.