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)$?
Maximum chromatic number of sparse graphs
algorithms;graphs
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}$.