Importance: Medium ✭✭
 Author(s): Wood, David R.
 Subject: Graph Theory » Coloring
 Keywords: degenerate girth
 Posted by: David Wood on: March 16th, 2014
 Solved by: A. V. Kostochka and J. Nesetril, Properties of Descartes' construction of triangle-free graphs with high chromatic number, Combin. Prob. Comput. 8 (1999), 467-472.
Question   Does there exist a -degenerate graph with chromatic number and girth , for all and ?

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.