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.