On the Number of Maximal Independent Sets in a Graph

Jesper Makholm Nielsen

April 2002

Abstract:

We show that the number of maximal independent sets of size exactly $k$ in any graph of size $n$ is at most $\lfloor n/k \rfloor^{k-(n\bmod k)} (\lfloor n/k \rfloor +1)^{n\bmod k}$. For maximal independent sets of size at most $k$ the same bound holds for $k\leq n/3$. For $k>n/3$ a bound of approximately $3^{n/3}$ is given. All the bounds are exactly tight and improve Eppstein (2001) who give the bound $3^{4k-n}4^{n-3k}$ on the number of maximal independent sets of size at most $k$, which is the same for $n/4 \leq k \leq n/3$, but larger otherwise. We give an algorithm listing the maximal independent sets in a graph in time proportional to these bounds (ignoring a polynomial factor), and we use this algorithm to construct algorithms for 4- and 5- colouring running in time ${\cal O}(1.7504^n)$ and ${\cal O}(2.1593^n)$, respectively

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.