patternMinor
Connection between max independent set and graph coloring
Viewed 0 times
coloringgraphindependentbetweenmaxandsetconnection
Problem
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?
Solution
Let $n$ be the number of vertices of a graph $G$, $\chi(G)$ be its chromatic number, and $\alpha(G)$ be the size of its maximum independent set. Then
$$
\alpha(G) \chi(G) \geq n.
$$
The reason is that every color class in a legal coloring is an independent set.
The bound can be tight – simple examples are complete graphs ($\alpha(G) = 1$ and $\chi(G) = n$) and empty graphs ($\alpha(G) = n$ and $\chi(G) = 1$). More generally, if $G$ is a union of $m$ many $n/m$-cliques, then $\alpha(G) = m$ while $\chi(G) = n/m$; and if $G$ is a complete $m$-partite graph in which all parts have size $n/m$, then $\alpha(G) = n/m$ and $\chi(G) = m$.
The bound can also be far from tight. A simple example is the union of an independent set of size $n/2$ and a clique of size $n/2$: $\alpha(G) = n/2+1$ and $\chi(G) = n/2$.
$$
\alpha(G) \chi(G) \geq n.
$$
The reason is that every color class in a legal coloring is an independent set.
The bound can be tight – simple examples are complete graphs ($\alpha(G) = 1$ and $\chi(G) = n$) and empty graphs ($\alpha(G) = n$ and $\chi(G) = 1$). More generally, if $G$ is a union of $m$ many $n/m$-cliques, then $\alpha(G) = m$ while $\chi(G) = n/m$; and if $G$ is a complete $m$-partite graph in which all parts have size $n/m$, then $\alpha(G) = n/m$ and $\chi(G) = m$.
The bound can also be far from tight. A simple example is the union of an independent set of size $n/2$ and a clique of size $n/2$: $\alpha(G) = n/2+1$ and $\chi(G) = n/2$.
Context
StackExchange Computer Science Q#109188, answer score: 3
Revisions (0)
No revisions yet.