Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Data Structures, WADS 2001
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 34k−n 4n−3k maximal independent sets I ⊂ G with |I| ≤ k, and that all such sets can be listed in time O(34k−n 4n−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 + 34/3/4)n) ≈ 2.4150n, improving a previous O((1+31/3)n) ≈ 2.4422n algorithm of Lawler (1976).