k-Färbung ist schneller als die Berechnung der chromatischen Zahl

k-Coloring is Faster than Computing the Chromatic Number

Or Zamir beweist, dass die k-Färbung von Graphen mit n Knoten einen randomisierten Algorithmus mit Laufzeit (2−ε_k)^n für jedes feste k besitzt, wobei ε_k > 0. Zuvor waren nur für k ≤ 6 schnellere Lösungen bekannt als der allgemeine O*(2^n)-Algorithmus von Björklund, Husfeldt und Koivisto (SICOMP 2009) zur Berechnung der chromatischen Zahl. Durch die Verallgemeinerung und Kombination von Werkzeugen aus der Reduktion von (k+2)-Färbung auf k-Listenfärbung (Zamir, ICALP 2021) und dem auf Hypergraph-Containern basierenden Ansatz (Zamir, STOC 2023) sowie neuen Algorithmen für Listenfärbungs-Instanzen mit gemischten langen und kurzen Farblisten erhält er eine iterierbare Reduktion von (k+1)-Listenfärbung auf k-Listenfärbung über festen Paletten.