Small Maximal Independent Sets and Faster Exact Graph Coloring

Original · EN

We show that, for any n-vertex graph G and integer parameter k, there are at most 3⁴ᵏ⁻ⁿ4ⁿ⁻³ᵏ maximal independent sets I ⊂ G with |I| <= k, and that all such sets can be listed in time O(3⁴ᵏ⁻ⁿ 4ⁿ⁻³ᵏ). 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)ⁿ) = 2.4150ⁿ, improving a previous O((1+3¹/³)ⁿ) = 2.4422ⁿ algorithm of Lawler (1976).