Is there any connection between the size of the largest independent set in a graph, and the minimum number of colors required to color the graph? I know that we can potentially color all the vertices in the largest independent set in the same color, but we know nothing about the rest of the vertices (besides being a vertex cover). Am I wrong?


There are relationships in the form of inequalities involving number of vertices $n(G)$ of a graph $G$.

Let $\alpha(G)$ be the size of a maximal independent set in $G$ and $\chi(G)$ the chromatic number, that is the smallest number of colors needed to color a graph $G$. Then obviously

$$ \chi(G) + \alpha(G) \leq n + 1, $$ since we can obtain one coloring with $n - \alpha(G) + 1$ colors, if we color all the vertices in the maximum independent set with one color and the remaining vertices with pairwise distinct colors.

In any G it trivially holds: $$ n(G) \leq \chi(G) \cdot \alpha(G) \tag{1} $$

and from this we also get $$ 2 \sqrt{n(G)} \leq \chi(G) + \alpha(G), $$ because we can expand $$ 0 \leq \left(\sqrt{\chi(G)} - \sqrt{\alpha(G)} \right)^{2} \\ 0 \leq \chi(G) - 2 \sqrt{\chi(G) \cdot \alpha(G)} + \alpha(G) $$ and use (1) to get $$ 2 \sqrt{n(G)} \leq \chi(G) + \alpha(G). $$ Combining both inequalities we get $$ 2 \sqrt{n(G)} \leq \chi(G) + \alpha(G) \leq n(G) + 1. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.