TY - JOUR
AU - Nielsen, Jesper Makholm
PY - 2002/04/05
Y2 - 2023/09/29
TI - On the Number of Maximal Independent Sets in a Graph
JF - BRICS Report Series
JA - BRICS
VL - 9
IS - 15
SE - Articles
DO - 10.7146/brics.v9i15.21733
UR - https://tidsskrift.dk/brics/article/view/21733
SP -
AB - We show that the number of maximal independent sets of size <em>exactly</em> k in any graph of size n is at most [ n/k ]^{k-(n mod k)} ([ n/k ] +1)^{n mod k}. For maximal independent sets of size <em>at most</em> 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-n}4^{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^n) and O(2.1593^n), respectively.
ER -