We show that the number of maximal independent sets of size
exactly ![$k$](Abs/img1.gif)
in any graph of size
![$n$](Abs/img2.gif)
is at most
![$\lfloor n/k
\rfloor^{k-(n\bmod k)} (\lfloor n/k \rfloor +1)^{n\bmod k}$](Abs/img3.gif)
. For maximal
independent sets of size
at most ![$k$](Abs/img1.gif)
the same bound holds for
![$k\leq
n/3$](Abs/img4.gif)
. For
![$k>n/3$](Abs/img5.gif)
a bound of approximately
![$3^{n/3}$](Abs/img6.gif)
is given. All the bounds
are exactly tight and improve Eppstein (2001) who give the bound
![$3^{4k-n}4^{n-3k}$](Abs/img7.gif)
on the number of maximal independent sets of size at most
![$k$](Abs/img1.gif)
, which is the same for
![$n/4 \leq k \leq n/3$](Abs/img8.gif)
, 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)$](Abs/img9.gif)
and
![${\cal O}(2.1593^n)$](Abs/img10.gif)
, respectively