# r-chromatic graphs with sufficient girth

For $k,l$ positive integers let $h(k,l)$ be the least integer with the property that in a graph on $h(k,l)$ vertices either there is a closed circuit of $k$ or fewer lines, or the graph contains $l$ independent points.

It is given that for sufficiently large $l$, that $h(k,l)>l^{1+1/2k}$.

Now how do we conclude from here that for all $r$, there is an $r$-chromatic graph with no $k$-polygon in it?

Clearly a graph on $\lfloor r^{1+1/2k}\rfloor$ vertices will not have a $k$-polygon in it, but how can we construct it in such a way that it is also $r$-chromatic?

-
Homework? mathoverflow.net/faq – Thomas Kalinowski May 4 '11 at 15:24
No it isnt homework. I am trying to read from a paper by Erdos. – Shahab May 5 '11 at 8:05
If you want to get a graph that has girth at least $k$ and needs at least $r$ colors, take an $n$ (number of vertices) so large that $nr^{1+1/2k}\leqslant n^{1+1/2k}$ and apply your given inequality with $l=n/r$. – Thomas Kalinowski May 5 '11 at 8:35
@ThomasKalinowski Why not leave this comment as an answer? – Yemon Choi Jun 3 at 13:20

To get a graph that has girth at least $k$ and needs at least $r$ colors, take an $n$ (number of vertices) so large that $nr^{1+1/2k}\leqslant n^{1+1/2k}$ and apply your given inequality with $l=n/r$.