mathimatikoi.org

Let \(G\) be a graph on \(n\) vertices and let \(\bar{G}\) denote its complement. Show that \[\chi(G) + \chi(\bar{G}) \geqslant 2\sqrt{n}.\] Show also that equality can be achieved whenever \(n\) is a perfect square.

Let \( k = \chi(G) \) and \( \bar{k} = \chi(\bar{G}) \). Consider a \(k\)-coloring of \(G\) and denote by \(n_i \) the number of vertices given the color \(i\) for \( i = 1,2, \ldots, k \). Let \(j \in \left\{ {1,2, \ldots ,k} \right\}\) be such that \({n_j} = \max \left\{ {{n_1},{n_2}, \ldots ,{n_k}} \right\}\). Clearly, we have \(n = \sum\limits_{i = 1}^k {{n_i}} \), hence
\[{n_j} \ge \frac{n}{k}.\]
If two vertices are given the same color in \(G\), then the edge they determine must be in the complementary graph \( \bar{G} \) and they must be given different colors in \( \bar{G} \). It follows that
\[\bar k \ge {n_j}.\]
Therefore, \(\bar k \ge \dfrac{n}{k}\) and
\[\boxed{\chi \left( G \right) \cdot \chi \left( {\bar G} \right) \ge n}.\]
Now, the arithmetic-geometric mean inequality implies that
\[\chi \left( G \right) + \chi \left( {\bar G} \right) \ge 2\sqrt {\chi \left( G \right) \cdot \chi \left( {\bar G} \right)} \ge 2\sqrt n \]
and the result follows.

To see that the equality can be achieved, let \( n = m^2 \). Divide the \( n \) vertices into \( m \) groups, where the vertices in each group are given the same color (so \( m \) colors are used). The edges of \( G \) are defined to be those joining vertices of different colors. Clearly, \[\chi \left( G \right) = \chi \left( {\bar G} \right) = m = \sqrt n ,\] so \[\chi \left( G \right) + \chi \left( {\bar G} \right) = 2\sqrt n .\]