It is currently Thu Jan 17, 2019 10:09 pm

 All times are UTC [ DST ]

 Page 1 of 1 [ 2 posts ]
 Print view Previous topic | Next topic
Author Message
 Posted: Mon Jan 18, 2016 4:10 am

Joined: Mon Nov 09, 2015 11:52 am
Posts: 77
Location: Limassol/Pyla Cyprus
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.

Top

 Posted: Mon Jan 18, 2016 4:11 am

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

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 2 posts ]

 All times are UTC [ DST ]

#### Mathimatikoi Online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Algebra    Linear Algebra    Algebraic Structures    Homological Algebra Analysis    Real Analysis    Complex Analysis    Calculus    Multivariate Calculus    Functional Analysis    Measure and Integration Theory Geometry    Euclidean Geometry    Analytic Geometry    Projective Geometry, Solid Geometry    Differential Geometry Topology    General Topology    Algebraic Topology Category theory Algebraic Geometry Number theory Differential Equations    ODE    PDE Probability & Statistics Combinatorics General Mathematics Foundation Competitions Archives LaTeX    LaTeX & Mathjax    LaTeX code testings Meta