Connection between max independent set and graph coloring

Question

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?

Answer 1

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. $$