2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Homework? mathoverflow.net/faq $\endgroup$
    – Thomas Kalinowski
    Commented May 4, 2011 at 15:24
  • $\begingroup$ No it isnt homework. I am trying to read from a paper by Erdos. $\endgroup$
    – user14875
    Commented May 5, 2011 at 8:05
  • $\begingroup$ 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$. $\endgroup$
    – Thomas Kalinowski
    Commented May 5, 2011 at 8:35
  • 2
    $\begingroup$ @ThomasKalinowski Why not leave this comment as an answer? $\endgroup$
    – Yemon Choi
    Commented Jun 3, 2016 at 13:20

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.