Small Maximal Independent Sets and Faster Exact Graph Coloring

2000/11/06 by David Eppstein
Computer Science · Mathematics · #cs.DS #math.CO

paper · pdf

published as J. Graph Algorithms & Applications 7(2):131-140, 2003 · 8 pages

arxiv created 2000/11/06 · arxiv updated 2009/11/30

Abstract

We show that, for any n-vertex graph G and integer parameter k, there are at most 3^4k-n4^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)ⁿ) ~= 2.4150ⁿ, improving a previous O((1+3^1/3)ⁿ) ~= 2.4422ⁿ algorithm of Lawler (1976).

Related

• Faster Graph Coloring in Polynomial Space
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time
• Independent Sets in n-vertex k-chromatic, ℓ-connected graphs
• An O^*(1.0821ⁿ)-Time Algorithm for Computing Maximum Independent Set in Graphs with Bounded Degree 3
• Exact Complexity of Exact-Four-Colorability