Small Maximal Independent Sets and Faster Exact Graph Coloring
Vol. 7, no. 2, pp. 131-140, 2003. Regular paper.
Abstract We show that, for any n-vertex graph G and integer parameter k, there are at most 34kn 4n−3k maximal independent sets IG with |I| ≤ k, and that all such sets can be listed in time O(34kn 4n−3k). These bounds are tight when n/4 ≤ kn/3. As a consequence, we show how to compute the exact chromatic number of a graph in time O((4/3 + 34/3/4)n) ≈ 2.4150n, improving a previous O((1+31/3)n) ≈ 2.4422n algorithm of Lawler (1976).
Submitted: October 2001.
Revised: April 2002.
Communicated by Giuseppe Liotta and Ioannis G. Tollis
article (PDF)