[Solved]: Maximum chromatic number of sparse graphs

Problem Detail: 

It is well-known that the chromatic number of a graph can be as high as $n$.

But what is the maximum chromatic number of a graph with $m = O(n)$?

Asked By : n.Perception

Answered By : Yuval Filmus

A graph with $O(n)$ edges has chromatic number $O(\sqrt{n})$, and this is tight.

Suppose first that a graph has $m = O(n)$ edges and chromatic number $\chi$. Take a $\chi$-coloring of the graph. Any two color classes must be connected by an edge, since otherwise we can identify them. Therefore $m \geq \binom{\chi}{2} = \Omega(\chi^2)$, and so $\chi = O(\sqrt{n})$.

To show that this is tight, consider the union of a clique on $\sqrt{n}$ vertices and an independent set on $n-\sqrt{n}$ vertices. This is a graph with $n$ vertices and $\binom{\sqrt{n}}{2} = O(n)$ edges, and chromatic number $\sqrt{n}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37660

3.2K people like this

 Download Related Notes/Documents