Sum of the chromatic numbers of a graph and its complement
-
- Former Team Member
- Posts: 77
- Joined: Mon Nov 09, 2015 12:52 pm
- 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
- Posts: 4
- Joined: Wed Nov 11, 2015 7: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 .\]
\[{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 .\]
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
Sign in
Who is online
Users browsing this forum: No registered users and 1 guest