Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00064
Small Maximal Independent Sets and Faster Exact Graph Coloring
Vol. 7, no. 2, pp. 131140, 2003. Regular paper.
Abstract We show that, for any nvertex graph G and integer parameter k,
there are at most 3^{4k−n} 4^{n−3k}
maximal independent sets I ⊂ G with I ≤ k, and that all
such sets can be listed in time
O(3^{4k−n} 4^{n−3k}). These bounds are tight when n/4 ≤ k ≤ n/3. As a consequence, we show how to compute the exact chromatic
number of a graph in time O((4/3 + 3^{4/3}/4)^{n}) ≈ 2.4150^{n},
improving a previous
O((1+3^{1/3})^{n}) ≈ 2.4422^{n} algorithm of Lawler (1976).
