#### Theory Seminar

# Breaking the 2^n barrier for 5-coloring and 6-coloring

Or ZamirInstitute for Advanced Studies

WHEN:

Friday, November 5, 2021 @ 3:00 pm - 4:00 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

WEB: Event Website

SHARE:

The coloring problem (i.e., computing the chromatic number of a graph) can be solved in O*(2^n) time, as shown by Björklund, Husfeldt and Koivisto in 2009. For k=3,4, better algorithms are known for the k-coloring problem. 3-coloring can be solved in O(1.33^n) time (Beigel and Eppstein, 2005) and 4-coloring can be solved in O(1.73^n) time (Fomin, Gaspers and Saurabh, 2007). Surprisingly, for k>4 no improvements over the general O*(2^n) are known. We show that both 5-coloring and 6-coloring can also be solved in O((2−ε)^n) 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−ε)^n) time, for some ε=ε_{Δ,α}>0.