Abstract
The coloring problem (i.e., computing the chromatic number of a graph) can be solved in O^*(2ⁿ) time, as shown by Björklund, Husfeldt and Koivisto in 2009. For k = 3,4, better algorithms are known for the kcoloring problem. 3coloring can be solved in O(1.33ⁿ) time (Beigel and Eppstein, 2005) and 4coloring can be solved in O(1.73ⁿ) time (Fomin, Gaspers and Saurabh, 2007). Surprisingly, for k > 4 no improvements over the general O^*(2ⁿ) are known. We show that both 5coloring and 6coloring can also be solved in O((2ε) ⁿ) time for some ε > 0. As a crucial step, we obtain an exponential improvement for computing the chromatic number of a very large family of graphs. In particular, for any constants Δ,α > 0, the chromatic number of graphs with at least α⋅ n vertices of degree at most Δ can be computed in O((2ε) ⁿ) time, for some ε = ε_{Δ,α} > 0. This statement generalizes previous results for boundeddegree graphs (Björklund, Husfeldt, Kaski, and Koivisto, 2010) and graphs with bounded average degree (Golovnev, Kulikov and Mihajlin, 2016). We generalize the aforementioned statement to List Coloring, for which no previous improvements are known even for the case of boundeddegree graphs.
BibTeX  Entry
@InProceedings{zamir:LIPIcs.ICALP.2021.113,
author = {Zamir, Or},
title = {{Breaking the 2ⁿ Barrier for 5Coloring and 6Coloring}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {113:1113:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14182},
URN = {urn:nbn:de:0030drops141825},
doi = {10.4230/LIPIcs.ICALP.2021.113},
annote = {Keywords: Algorithms, Graph Algorithms, Graph Coloring}
}
Keywords: 

Algorithms, Graph Algorithms, Graph Coloring 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 