proof of chromatic number and girth

Let α(G) denote the size of the largest independent set in G, and χ(G) the chromatic numberMathworldPlanetmath of G. We want to show that there is a graph G with girth larger than and χ(G)>k, for any ,k>0.

We first prove the following claim.

Claim: Given a positive integer and a positive real number t<1/, for all sufficiently large n, there is a graph G on n vertices satisfying properties

  1. 1.

    the number of cycles of length at most is less than n/2,

  2. 2.


Proof of claim: Let G be a random graphMathworldPlanetmath on n vertices, in which each pair of vertices joint by an edge independently with probability p=nt-1. Let X be the number of cycles of length at most in G. The expected value of X is

E[X] =i=3n(n-1)(n-i+1)2ipi

By Markov inequality,


we have


as n, since t<1.

On the other hand, let y=(3logn)/p, and Y be the number of independent sets of size y in G. By Markov inequality again,




Using the inequalities, (ny)<ny and (1-p)e-p, we get


Our choice of y guarantees that ne-p(y-1)/2<β<1 for some β, and y as n approaches infinity. Therefore,

Pr(α(G)y)0,as n.

We can thus find n0 such that for all n>n0, both Pr(Xn/2) and Pr(α(G)y) are strictly less than 1/2. For all n>n0,

Pr(X< and α(G)<y)>1-Pr(X)-Pr(α(G)y)>1.

Therefore there exists a graph that satisfies the two properties in the claim. This ends the proof of the claim.

Let G be a graph that satisfies the two properties in the claim. Remove a vertex from each cycle of length at most in G. The resulting graph G has girth larger than , more than n/2 vertices, and α(G)α(G). Sinceχ(G)α(G)|G|, we have


We can pick sufficiently large n such that χ(G) is larger than k. Then the chromatic number of G is larger than k and girth is larger than .

Reference: N. Alon and J. Spencer, The probabilistic method, 2nd, John Wiley.

Title proof of chromatic number and girth
Canonical name ProofOfChromaticNumberAndGirth
Date of creation 2013-03-22 14:31:02
Last modified on 2013-03-22 14:31:02
Owner kshum (5987)
Last modified by kshum (5987)
Numerical id 9
Author kshum (5987)
Entry type Proof
Classification msc 05C38
Classification msc 05C15
Classification msc 05C80