Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi. For k,l positive integers let h(k,l) be the least integer with the property that in graph on h(k,l) vertices either there is a closed circuit of k or fewer lines or that the graph contains l independent points. It is given that for sufficiently large l, 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 floor(r^{1+1/2k}) 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?

share|cite|improve this question
Homework? – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.