TY - JOUR
AU - Byskov, Jesper Makholm
PY - 2002/12/05
Y2 - 2022/11/29
TI - Chromatic Number in Time O(2.4023^n) Using Maximal Independent Sets
JF - BRICS Report Series
JA - BRICS
VL - 9
IS - 45
SE - Articles
DO - 10.7146/brics.v9i45.21760
UR - https://tidsskrift.dk/brics/article/view/21760
SP -
AB - 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).
ER -