ALCOMFT-TR-03-78

Jesper Makholm Byskov
Chromatic Number in Time O(2.4023ⁿ) Using Maximal Independent Sets
Århus. Work package 4. November 2003.

Abstract: In this paper we improve an algorithm by Eppstein (2001) for finding the chromatic number of a graph. We modify the algorithm slightly, and by using a bound on the number of maximal independent sets of size k from our recent paper (2003), we prove that the running time is O(2.4023ⁿ). Eppstein's algorithm runs in time O(2.4150ⁿ). The space usage for both algorithms is O(2ⁿ).

Postscript file: ALCOMFT-TR-03-78.ps.gz (319 kb).