Sum of the chromatic numbers of a graph and its complement

Combinatorics
Post Reply
Demetres
Former Team Member
Former Team Member
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

#1

Post by Demetres »

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
Former Team Member
Posts: 4
Joined: Wed Nov 11, 2015 6:18 am

Re: Sum of the chromatic numbers of a graph and its compleme

#2

Post by Vangelis Mouroukos »

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 .\]
Post Reply

Create an account or sign in to join the discussion

You need to be a member in order to post a reply

Create an account

Not a member? register to join our community
Members can start their own topics & subscribe to topics
It’s free and only takes a minute

Register

Sign in

Who is online

Users browsing this forum: No registered users and 3 guests