Chromatic Number in Time $O(2.4023^n)$ Using Maximal Independent Sets

Jesper Makholm Byskov

December 2002

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^n)$. Eppstein's algorithm runs in time $O(2.4150^n)$. The space usage for both algorithms is $O(2^n)$

Available as PostScript, PDF.

Last modified: 2003-06-08 by webmaster.