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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
|
||||||||||
|
