Welcome to mathimatikoi.org forum; Enjoy your visit here.

## Sum of the chromatic numbers of a graph and its complement

Combinatorics
Demetres
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.
Vangelis Mouroukos
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 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 .$