k-Kleurbaarheid is sneller dan het berekenen van het chromatisch getal

Samenvatting

We bewijzen dat $k$-kleurbaarheid op grafen met $n$-vertices een gerandomiseerd algoritme heeft met een looptijd van $(2-\varepsilonk)^n$, waarbij $\varepsilonk>0$ voor elke vaste $k$. Voorheen was alleen bekend dat de gevallen $k\leq 6$ snellere oplossingen hadden dan het algemene $O^\star(2^n)$ tijdsalgoritme van [Björklund, Husfeldt, Koivisto, SICOMP 2009] dat het chromatisch getal berekent.

We lossen dit langlopende open probleem op door instrumenten te generaliseren en te combineren uit de reductie van $(k+2)$-kleuring naar $k$-lijstkleuring van [Zamir, ICALP 2021] en de benadering op basis van hypergraaf-containers in [Zamir, STOC 2023]. Samen met nieuwe algoritmen voor lijstkleuringsinstanties die lange en korte kleurlijsten mengen, levert dit een itereerbare reductie op van $(k+1)$-lijstkleuring naar $k$-lijstkleuring over vaste paletten.