Chromatic Number in Time O(2.4023^n) Using Maximal Independent Sets
AbstractIn 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).
How to Cite
Byskov, J. M. (2002). Chromatic Number in Time O(2.4023^n) Using Maximal Independent Sets. BRICS Report Series, 9(45). https://doi.org/10.7146/brics.v9i45.21760
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.