1
$\begingroup$

Definitions:

  1. The independence number $\alpha(G)$ is the maximum size of an independent set of $G$.

  2. A coloring of $G$ is a partition of the vertices into (induced) independent sets (colors), and the chromatic number $\chi(G)$ is the smallest number of colors possible in a coloring of $G$.

What is the relation between $\chi(\bar{G})$ and $\alpha(G)$ for any graph?, where $\bar G$ is complement of $G$.

$\endgroup$

closed as off-topic by Math1000, Silvia Ghinassi, Chris Godsil, user296602, Harish Chandra Rajpoot Feb 26 '16 at 8:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Math1000, Silvia Ghinassi, Chris Godsil, Community, Harish Chandra Rajpoot
If this question can be reworded to fit the rules in the help center, please edit the question.

2
$\begingroup$

If you take the complement, an independent set becomes a clique. Hence in $\bar{G}$, there is a $K_{\alpha (G)}$ subgraph.

It is known that you can not color a clique of size $k$ with less than $k$ colors, thus $$ \chi(\bar{G}) \geq \alpha (G). $$

$\endgroup$
  • $\begingroup$ If $G$ is a circle of $n$ points, $\alpha(G) = n-1$ and $\bar{G}$ is a $K_n$ without a circle. You can color $\bar{G}$ with $n-1$ colors since you can choose the same color for the end vertices of an arbitrary edge of $G$. $\endgroup$ – MCsikos Feb 26 '16 at 0:32
  • $\begingroup$ Unfortunately I didn't think about more examples, where the equality holds. For sure it doesn't hold for any graph since if $\bar{G}$ is an odd cycle, $\alpha (G)=2$ but $\chi (\bar{G}) = 3$. Is the proof and this example clear for you? $\endgroup$ – MCsikos Feb 26 '16 at 0:43
  • 1
    $\begingroup$ In fact equality holds if and only if the clique number of $\bar{G}$ is equal to the chromatic number of $\bar{G}$, maybe you can find some tables online which list these numbers for well known graphs. $\endgroup$ – MCsikos Feb 26 '16 at 0:47