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.

the number of cycles of length at most $\ell$ is less than $n/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}$

By Markov inequality,

$\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}<n^{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)<y)>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, 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