Small Maximal Independent Sets and Faster Exact Graph Coloring
<|reference_start|>Small Maximal Independent Sets and Faster Exact Graph Coloring: We show that, for any n-vertex graph G and integer parameter k, there are at most 3^{4k-n}4^{n-3k} maximal independent sets I \subset 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)^n) ~= 2.4150^n, improving a previous O((1+3^{1/3})^n) ~= 2.4422^n algorithm of Lawler (1976).<|reference_end|>
@article{eppstein2000small,
    title={Small Maximal Independent Sets and Faster Exact Graph Coloring},
    author={David Eppstein},
    journal={J. Graph Algorithms & Applications 7(2):131-140, 2003},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0011009},
    primaryClass={cs.DS math.CO}
}