4-regular 4-chromatic graphs of high girth
Status open medium confidence
The question whether 4-regular 4-chromatic graphs of arbitrarily high girth exist is still open. The general Grünbaum conjecture (every $m$-regular $m$-chromatic graph class admits arbitrarily high girth) is known to be false from Johansson's $\chi \le C\Delta/\log\Delta$ bound for triangle-free graphs, but that bound does not preclude the small-$m$ case considered here. Only a handful of 4-regular 4-chromatic graphs of girth $\ge 4$ are known (Chvátal at girth 4; Brinkmann and Grünbaum at girth 5); no construction or non-existence proof for higher girth has appeared in the searched literature.
Reviewer notes. Searches surfaced Bucić–Davies (arXiv:2312.06898, 2023) on geometric graphs with exponential chromatic number and arbitrary girth, but that paper does not address the regular-graph version of the question, so it is not cited as evidence here. Status 'medium' rather than 'high' because absence of recent constructions in search results is not conclusive.
Discussion
Grunbaum conjectured that for every $ m $ , there exist $ m $ -regular $ m $ -chromatic graphs of arbitrarily high girth. However, this was shown dramatically false by Johansson, who proved that every triangle free graph $ G $ with maximum degree $ \Delta $ satisfies $ \chi(G) \le C \frac{\Delta}{\log \Delta} $ for some fixed constant $ C $ . 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 $ \ge 4 $ 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 $ \le 6 $ and arbitrarily high girth, but it is open wether there exist 4-chromatic graphs of minimum degree 5 and arbitrary girth.