# Colouring $d$-degenerate graphs with large girth (Solved)

**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.