# 4-regular 4-chromatic graphs of high girth

**Problem**Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?

Grunbaum conjectured that for every , there exist -regular -chromatic graphs of arbitrarily high girth. However, this was shown dramatically false by Johansson, who proved that every triangle free graph with maximum degree satisfies for some fixed constant . Neverless, some interesting smaller cases of Grunbaum's conjecture, such as the one highlighted above, might still be true.

There are only a few 4-regular 4-chromatic graphs of girth which are known. These include the Chvatal graph, Brinkmann graph (discovered independently by Kostochka), and Grunbaum graph. To the best of my (M. DeVos') knowledge, this might be the full list of such graphs.

There do exist 4-chromatic graphs of minimum degree and arbitrarily high girth, but it is open wether there exist 4-chromatic graphs of minimum degree 5 and arbitrary girth.

## Bibliography

* indicates original appearance(s) of problem.

### What about higher degree?

What maximum degree is needed in a triangle-free graph (or higher girth) with chromatic number 5? What about chromatic number 6 and 7? Are good bounds known on these maximum degrees?

## The list of known graphs is not full

Your list of 4 regular 4 chromatic graphs with girth >= 4 is not complete. Check "A note on 4-regular 4 chromatic graphs with girth 4" http://math.nju.edu.cn/~zkmfl/kmzhang/41-60/Zhang44.pdf. Girth 5 is known too.