Small Maximal Independent Sets and Faster Exact Graph Coloring

Abstract

We show that, for any n-vertex graph G and integer parameter k, there are at most 34k−n4n−3k maximal independent sets I ⊂ G with |I | ≤ k, and that all such sets can be listed in time O(34k−n4n−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). 1