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)$?


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}$.

  • $\begingroup$ Somehow throwing in enough isolated vertices until the statement fits does seem a little like circumventing the intention of the question (while formally it's obviously correct), which is probably why some definitions of sparse graphs also make statements about the maximal number of edges in any subgraph. $\endgroup$ – G. Bach Jan 27 '15 at 23:42
  • $\begingroup$ @G.Bach If the maximal degree is $\Delta$ then the maximal chromatic number is $\Delta+1$. That's a very stringent definition of sparsity, though, and one wonders what happens for graphs in which $E = O(V)$ for all sets of vertices of size at least $m$. $\endgroup$ – Yuval Filmus Jan 28 '15 at 2:37
  • $\begingroup$ Did you mean minimal chromatic number? When you say stringent definition of sparsity, which one are you referring to? I did think of graphs with restrictions on the size of $E$ for all subgraphs, somehow that seems like a more interesting problem. $\endgroup$ – G. Bach Jan 28 '15 at 3:01
  • $\begingroup$ @G.Bach No, I did mean maximal chromatic number. The smaller $m$ is, the lower the upper bound on the chromatic number is. The stringent definition of sparsity is that the local neighborhood at each vertex is small, that is, the maximal degree is small. I then suggested a less stringent definition, depending on a parameter $m$. One can think of other definitions. $\endgroup$ – Yuval Filmus Jan 28 '15 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.