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 |

Last modified: 2003-06-08 by webmaster.