proof of chromatic number and girth
We first prove the following claim.
Claim: Given a positive integer and a positive real number , for all sufficiently large , there is a graph on vertices satisfying properties
the number of cycles of length at most is less than ,
Proof of claim: Let be a random graph on vertices, in which each pair of vertices joint by an edge independently with probability . Let be the number of cycles of length at most in . The expected value of is
as , since .
On the other hand, let , and be the number of independent sets of size in . By Markov inequality again,
Using the inequalities, and , we get
Our choice of guarantees that for some , and as approaches infinity. Therefore,
We can thus find such that for all , both and are strictly less than . For all ,
Therefore there exists a graph that satisfies the two properties in the claim. This ends the proof of the claim.
Let be a graph that satisfies the two properties in the claim. Remove a vertex from each cycle of length at most in . The resulting graph has girth larger than , more than vertices, and . Since http://planetmath.org/node/6037, we have
We can pick sufficiently large such that is larger than . Then the chromatic number of is larger than and girth is larger than .
Reference: N. Alon and J. Spencer, The probabilistic method, 2nd, John Wiley.
|Title||proof of chromatic number and girth|
|Date of creation||2013-03-22 14:31:02|
|Last modified on||2013-03-22 14:31:02|
|Last modified by||kshum (5987)|