Welcome to mathimatikoi.org forum; Enjoy your visit here.
Sum of the chromatic numbers of a graph and its complement

 Former Team Member
 Articles: 0
 Posts: 77
 Joined: Mon Nov 09, 2015 11:52 am
 Location: Limassol/Pyla Cyprus
 Contact:
Sum of the chromatic numbers of a graph and its complement
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.

 Former Team Member
 Articles: 0
 Posts: 4
 Joined: Wed Nov 11, 2015 6:18 am
Re: Sum of the chromatic numbers of a graph and its compleme
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 arithmeticgeometric 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 .\]
\[{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 arithmeticgeometric 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 .\]