Seminar Details
Breaking the 2^n barrier for 5-coloring and 6-coloring
- Start Date: March 31, 2021
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Or Zamir - Institute for Advanced Study
- Event Location: Online Event
- Event Additional Info: <p>The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://sites.google.com/view/dimacs-theory-seminar/home">https://sites.google.com/view/dimacs-theory-seminar/home</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
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