k-Coloring es más rápido que calcular el número cromático
k-Coloring is Faster than Computing the Chromatic Number
Un nuevo algoritmo aleatorio resuelve el k-coloreo de grafos con n vértices en tiempo (2−ε_k)^n, donde ε_k>0 para cada k fijo. Anteriormente, solo se conocían soluciones más rápidas para k≤6. El resultado generaliza y combina herramientas de la reducción de (k+2)-coloreo a k-list-coloreo de Zamir (ICALP 2021) y el enfoque basado en contenedores de hipergrafos de Zamir (STOC 2023), junto con nuevos algoritmos para instancias de list-coloreo que mezclan listas largas y cortas. Esto produce una reducción iterable de (k+1)-list-coloreo a k-list-coloreo sobre paletas fijas.
Demostramos que el k-coloreo en grafos de n vértices tiene un algoritmo aleatorio que se ejecuta en tiempo (2−ε_k)^n, donde ε_k>0 para cada k fijo.