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?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ There’s always an independent set whose size is at least $n/\chi$, where $n$ is the number of vertices and $\chi$ is the chromatic number. This bound is tight, for example for complete graphs and for empty graphs. $\endgroup$– Yuval FilmusCommented May 10, 2019 at 14:44
-
1$\begingroup$ Define a graph $G=(V,A)$ where $V=M\cup M'$, where $M=[1,n]$, $M'=[n+1,2n]$, and $A=\{\{i,i+n\} \mid i\in[n]\}\cup A'$ for any subset $A'$ of edges between vertices in $M'$. Then $M$ is a maximum independent set of size $n$ in $G$ since for every pair of vertices $\{i,i+n\}$ at most one can be part of an independent set. The minimum number of colors of $G$ can vary between $2$ for $A'=\emptyset$ up to $n$ for $A'$ containing all possible edges. $\endgroup$– Marcus RittCommented May 10, 2019 at 14:47
-
$\begingroup$ There is always an optimal colouring in which at least one of the colours is a maximal independent set, since for any optimal colouring that does not have this property, you can pick any colour, and repeatedly move vertices from other colours to it until the property does hold. But in general there might be no optimal colouring that contains a maximum IS: e.g. the graph that is the inverse of $ab, bc, ca, aa', bb', cc'$ has a unique maximum IS of size 3 ($abc$), but including this forces the use of at least 4 colours; choosing 3 smaller ISes ($aa', bb', cc'$) enables a 3-colouring. $\endgroup$– j_random_hackerCommented May 10, 2019 at 16:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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$.
answered May 10, 2019 at 19:44
$\begingroup$
$\endgroup$
Each color class is an independent set, and so has size at most $\alpha(G)$, the maximum size of an independent set. Hence, the number of color classes needed to cover the vertex set $V(G)$ is at least $|V(G)/\alpha(G)$. Thus, the chromatic number is at least $|V(G)/\alpha(G)$.
