proof of chromatic number and girth
Let $\alpha (G)$ denote the size of the largest independent set in $G$, and $\chi (G)$ the chromatic number^{} of $G$. We want to show that there is a graph $G$ with girth larger than $\mathrm{\ell}$ and $\chi (G)>k$, for any $\mathrm{\ell},k>0$.
We first prove the following claim.
Claim: Given a positive integer $\mathrm{\ell}$ and a positive real number $$, for all sufficiently large $n$, there is a graph $G$ on $n$ vertices satisfying properties

1.
the number of cycles of length at most $\mathrm{\ell}$ is less than $n/2$,

2.
$$.
Proof of claim: Let $G$ be a random graph^{} on $n$ vertices, in which each pair of vertices joint by an edge independently with probability $p={n}^{t1}$. Let $X$ be the number of cycles of length at most $\mathrm{\ell}$ in $G$. The expected value of $X$ is
$E[X]$  $={\displaystyle \sum _{i=3}^{\mathrm{\ell}}}{\displaystyle \frac{n(n1)\mathrm{\cdots}(ni+1)}{2i}}{p}^{i}$  
$$ 
$$ 
we have
$$\mathrm{Pr}(X\ge n/2)\to 0$$ 
as $n\to \mathrm{\infty}$, since $$.
On the other hand, let $y=\lceil (3\mathrm{log}n)/p\rceil $, and $Y$ be the number of independent sets of size $y$ in $G$. By Markov inequality again,
$$\mathrm{Pr}(\alpha (G)\ge y)=\mathrm{Pr}(Y\ge 1)\le E[Y].$$ 
However,
$$E[Y]=\left(\genfrac{}{}{0pt}{}{n}{y}\right){(1p)}^{y(y1)/2}$$ 
Using the inequalities, $$ and $(1p)\le {e}^{p}$, we get
$$ 
Our choice of $y$ guarantees that $$ for some $\beta $, and $y\to \mathrm{\infty}$ as $n$ approaches infinity. Therefore,
$$\mathrm{Pr}(\alpha (G)\ge y)\to 0,\text{as}n\to \mathrm{\infty}.$$ 
We can thus find ${n}_{0}$ such that for all $n>{n}_{0}$, both $\mathrm{Pr}(X\ge n/2)$ and $\mathrm{Pr}(\alpha (G)\ge y)$ are strictly less than $1/2$. For all $n>{n}_{0}$,
$$ 
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 $\mathrm{\ell}$ in $G$. The resulting graph ${G}^{\prime}$ has girth larger than $\mathrm{\ell}$, more than $n/2$ vertices, and $\alpha ({G}^{\prime})\le \alpha (G)$. Since http://planetmath.org/node/6037$\mathrm{\chi}\mathtt{}\mathrm{(}{\mathrm{G}}^{\mathrm{\prime}}\mathrm{)}\mathtt{}\mathrm{\alpha}\mathtt{}\mathrm{(}{\mathrm{G}}^{\mathrm{\prime}}\mathrm{)}\mathrm{\ge}\mathrm{}{\mathrm{G}}^{\mathrm{\prime}}\mathrm{}$, we have
$$\chi ({G}^{\prime})\ge \frac{n/2}{3{n}^{1t}\mathrm{log}n}=\frac{{n}^{t}}{6\mathrm{log}n}$$ 
We can pick sufficiently large $n$ such that $\chi ({G}^{\prime})$ is larger than $k$. Then the chromatic number of ${G}^{\prime}$ is larger than $k$ and girth is larger than $\mathrm{\ell}$.
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  20130322 14:31:02 
Last modified on  20130322 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 