# Minimal graphs of prescribed girth and chromatic number

The well known result of Erdős, states that

Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$

What I am wondering is

When can we expect equality to hold? I.e for which parameters $(g,k)$ do we have graphs with girth $g$ and chromatic number $k$?

Of course we cannot have $k=2$ and $g$ odd, but are there any other more interesting pairs $(g,k)$ for which there does not exist a graph of girth $g$ and chromatic number number $k$? In particular

Has anyone thought of searching/classifying these graphs in an analogous way as cages for girth and degree?

After what Jacob said I propose the following

What is the smallest graph of girth $4$ and chromatic number $5.$

• Using your notation, there are easy examples for (3,k) and (k,3) for k at least 3. It might be instructive to establish an example for (k,k) as well. – The Masked Avenger Aug 28 '13 at 14:00
• Also, one can add smaller cycles to a k colored graph. So it is a matter of k coloring arbitrarily large girth graphs. – The Masked Avenger Aug 28 '13 at 15:11
• I think the question you want to ask is what are (bounds on) the functions v(g,k) and e(g,k), which count the smallest number of vertices respectively edges possible for a graph of girth g and chromatic number k. – The Masked Avenger Aug 28 '13 at 17:32