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 in any graph of size is at most . For maximal independent sets of size at most the same bound holds for . For a bound of approximately is given. All the bounds are exactly tight and improve Eppstein (2001) who give the bound on the number of maximal independent sets of size at most , which is the same for , 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 and , respectively

Available as PostScript, PDF, DVI.