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 $\ell$ and $\chi(G)>k$, for any $\ell,k>0$.

We first prove the following claim.

Claim: Given a positive integer $\ell$ and a positive real number $t<1/\ell$, 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 $\ell$ is less than $n/2$,

2. 2.

$\alpha(G)<3n^{1-t}\log n$.

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^{t-1}$. Let $X$ be the number of cycles of length at most $\ell$ in $G$. The expected value of $X$ is

 $\displaystyle E[X]$ $\displaystyle=\sum_{i=3}^{\ell}\frac{n(n-1)\cdots(n-i+1)}{2i}p^{i}$ $\displaystyle<\sum_{i=3}^{\ell}\frac{(np)^{i}}{2i}<\sum_{i=3}^{\ell}n^{ti}<% \ell n^{t\ell}$
 $\Pr(X\geq n/2)<2\ell n^{t\ell-1},$

we have

 $\Pr(X\geq n/2)\rightarrow 0$

as $n\rightarrow\infty$, since $t\ell<1$.

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

 $\Pr(\alpha(G)\geq y)=\Pr(Y\geq 1)\leq E[Y].$

However,

 $E[Y]={n\choose y}(1-p)^{y(y-1)/2}$

Using the inequalities, ${n\choose y} and $(1-p)\leq e^{-p}$, we get

 $\Pr(\alpha(G)\geq y)<(ne^{-p(y-1)/2})^{y}$

Our choice of $y$ guarantees that $ne^{-p(y-1)/2}<\beta<1$ for some $\beta$, and $y\rightarrow\infty$ as $n$ approaches infinity. Therefore,

 $\Pr(\alpha(G)\geq y)\rightarrow 0,\quad\text{as n\rightarrow\infty}.$

We can thus find $n_{0}$ such that for all $n>n_{0}$, both $\Pr(X\geq n/2)$ and $\Pr(\alpha(G)\geq y)$ are strictly less than $1/2$. For all $n>n_{0}$,

 $\Pr(X<\ell\text{ and }\alpha(G)1-\Pr(X\geq\ell)-\Pr(\alpha(G)\geq 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 $\ell$ in $G$. The resulting graph $G^{\prime}$ has girth larger than $\ell$, more than $n/2$ vertices, and $\alpha(G^{\prime})\leq\alpha(G)$. Since http://planetmath.org/node/6037$\chi(G^{\prime})\alpha(G^{\prime})\geq|G^{\prime}|$, we have

 $\chi(G^{\prime})\geq\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 larger than $k$. Then the chromatic number of $G^{\prime}$ is larger than $k$ and girth is larger than $\ell$.

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

Title proof of chromatic number and girth ProofOfChromaticNumberAndGirth 2013-03-22 14:31:02 2013-03-22 14:31:02 kshum (5987) kshum (5987) 9 kshum (5987) Proof msc 05C38 msc 05C15 msc 05C80