![](/files/happy5.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ d + 1 $](/files/tex/2b7e8b22bf0d4e0aa6cc7dcc6acf051bab97990f.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ d \geq 2 $](/files/tex/6dfe01f1d81a75b84c1284e30c319cc6137173b1.png)
![$ g \geq 3 $](/files/tex/58bd309cb5a84dc6bb041e8d02207c64d974c46d.png)
A graph is -degenerate if every subgraph has a vertex of degree at most
. Such graphs are
-colourable by a minimum-degree-greedy algorithm. This bound is tight for complete graphs. More interestingly, Alon-Krivelevich-Sudakov [AKS] proved that it is tight for triangle-free graphs. That is, there are
-degenerate triangle-free graphs with chromatic number
. Thus the answer to the above question is `yes' for
. Odd cycles show that the answer is `yes' for
and
. A `yes' answer for
and
would generalise the famous result of Erdős [E], who proved that there are
-chromatic graphs with girth
for all
and
. A `no' answer would also be interesting---this would provide a non-trivial upper bound on the chromatic number of
-degenerate graphs with girth
.
Bibliography
[AKS] Noga Alon, Michael Krivelevich, and Benny Sudakov. Coloring graphs with sparse neighborhoods. J. Combin. Theory Ser. B 77.1:73--82, 1999.
[E] Paul Erdős, Graph theory and probability, Canad. J. Math. 11:34--38, 1959.
*[W] David R. Wood, Hypergraph Colouring and Degeneracy, arXiv:1310.2972, 2013.
* indicates original appearance(s) of problem.