Prove that if G is a simple graph, $\chi \geq \frac{|V|^2}{|V|^2-2|E|}$

Solution 1:

This is a tough question.

The result was proved by Myers and Liu in this paper by induction.

Solution 2:

Let $G(V,E)$ be a simple graph on the finite vertex set $V$ with the edge set $E$. Write $v:=|V|$, $e:=|E|$, and $k:=\left\lceil\frac{v^2}{v^2-2e}\right\rceil$. Then, $k-1<\frac{v^2}{v^2-2e}$, or $$\left(\frac{k-2}{k-1}\right)\frac{v^2}{2}<e\,.$$ By Turán's Graph Theorem (see also here), $G$ has a $k$-clique. That means, the chromatic number of $G$ is at least $k$. In other words, $$\chi(G)\geq \omega(G)\geq \left\lceil\frac{v^2}{v^2-2e}\right\rceil\,.$$ Notice also that this bound is sharp. As $\left(\frac{k-1}{k}\right)\frac{v^2}{2}\geq e$, we can take $G$ to be a subgraph of the Turán graph $T(v,k)$ with $e$ edges so that both the clique number $\omega(G)$ and the chromatic number $\chi(G)$ of $G$ are equal to $k$.