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 showthat 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 realnumber , for all sufficiently large $n$, there is agraph $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 withprobability $p=n^{t-1}$. Let $X$ be the number of cycles of lengthat most $\mathrm{\ell }$ in $G$. The expected value of $X$ is

$E[X]$$={\displaystyle \sum _{i=3}^{\mathrm{\ell }}}{\displaystyle \frac{n(n-1)\mathrm{\cdots }(n-i+1)}{2i}}{p}^i$

By Markov inequality,

we have

$$\mathrm{Pr}(X\ge n/2)\to 0$$

as $n\to \mathrm{\infty }$, since .

On the other hand, let $y=\lceil (3\log n)/p\rceil$, and $Y$ bethe number of independent sets of size $y$ in $G$. By Markovinequality again,

$$\mathrm{Pr}(\alpha (G)\ge y)=\mathrm{Pr}(Y\ge 1)\le E[Y].$$

However,

$$E[Y]=\left(\genfrac{}{}{0pt}{}{n}{y}\right){(1-p)}^{y(y-1)/2}$$

Using the inequalities, and $(1-p)\le e^{-p}$, we get

Our choice of $y$ guarantees that for some $\beta$, and $y\to \mathrm{\infty }$ as $n$ approachesinfinity. 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 propertiesin the claim. This ends the proof of the claim.

Let $G$ be a graph that satisfies the two properties in theclaim. 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 }$, morethan $n/2$ vertices, and $\alpha (G^{\prime })\le \alpha (G)$. Sincehttp://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}{3n^{1-t}\log n}=\frac{n^t}{6\log n}$$

We can pick sufficiently large $n$ such that $\chi (G^{\prime })$ is largerthan $k$. Then the chromatic number of $G^{\prime }$ is larger than $k$ andgirth is larger than $\mathrm{\ell }$.

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