patternMinor
Maximum chromatic number of sparse graphs
Viewed 0 times
numbermaximumgraphschromaticsparse
Problem
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)$?
But what is the maximum chromatic number of a graph with $m = O(n)$?
Solution
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}$.
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}$.
Context
StackExchange Computer Science Q#37660, answer score: 6
Revisions (0)
No revisions yet.