ALCOMFT-TR-02-87

Jesper Makholm Nielsen
On the Number of Maximal Independent Sets in a Graph
Århus. Work package 4. May 2002.

Abstract: We show that the number of maximal independent sets of size exactly k in any graph of size n is at most \floor{ n/k }^{k-(n mod k)} (\floor{ n/k } +1)^{n mod k}. For maximal independent sets of size at most k the same bound holds for k<= 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-n4^n-3k on the number of maximal independent sets of size at most k, which is the same for n/4 <= k <= 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 O(1.7504ⁿ) and O(2.1593ⁿ), respectively.

Postscript file: ALCOMFT-TR-02-87.ps.gz (115 kb).