k-Coloring is Faster than Computing the Chromatic Number

# 𝑘-Coloring is Faster than Computing the Chromatic Number
Source: [https://arxiv.org/html/2607.25973](https://arxiv.org/html/2607.25973)
###### Abstract

We prove thatkk\-coloring onnn\-vertex graphs has a randomized algorithm running in time\(2−εk\)n,\(2\-\\varepsilon\_\{k\}\)^\{n\},whereεk\>0\\varepsilon\_\{k\}\>0for every fixedkk\. Previously, only the casesk≤6k\\leq 6were known to have faster solutions than the generalO∗​\(2n\)O^\{\*\}\\bigl\(2^\{n\}\\bigr\)time algorithm of \[Björklund, Husfeldt, Koivisto, SICOMP 2009\] that computes the chromatic number\.

We resolve this long\-standing open problem by generalizing and combining tools from the\(k\+2\)\(k\+2\)\-coloring tokk\-list\-coloring reduction of \[Zamir, ICALP 2021\] and the hypergraph\-containers based approach in \[Zamir, STOC 2023\]\. Together with new algorithms for list\-coloring instances mixing long and short color lists, this yields an iterable reduction from\(k\+1\)\(k\+1\)\-list\-coloring tokk\-list\-coloring over fixed palettes\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2607.25973#S1)
2. [2Overview](https://arxiv.org/html/2607.25973#S2)1. [2\.1Organization and reading guide](https://arxiv.org/html/2607.25973#S2.SS1)
3. [3Background](https://arxiv.org/html/2607.25973#S3)1. [3\.1Coloring, List Coloring, and Constraint Satisfaction Problems](https://arxiv.org/html/2607.25973#S3.SS1) 2. [3\.2From deciding colorability to finding a coloring](https://arxiv.org/html/2607.25973#S3.SS2) 3. [3\.3Normalization of list\-coloring instances](https://arxiv.org/html/2607.25973#S3.SS3) 4. [3\.4Coloring all induced subinstances for the price of one](https://arxiv.org/html/2607.25973#S3.SS4) 5. [3\.5Main tool I: Coloring with bounded\-degrees](https://arxiv.org/html/2607.25973#S3.SS5) 6. [3\.6Main tool II: Two\-block color restrictions and Extensions\-Sum](https://arxiv.org/html/2607.25973#S3.SS6)
4. [4Warm\-up: Extending the reduction from two to three steps](https://arxiv.org/html/2607.25973#S4)1. [4\.1The seed\-shortening lemma](https://arxiv.org/html/2607.25973#S4.SS1) 2. [4\.2Reducing to an instance with many size\-two lists](https://arxiv.org/html/2607.25973#S4.SS2) 3. [4\.3Interpolation algorithm for instances with many size\-two lists](https://arxiv.org/html/2607.25973#S4.SS3) 4. [4\.4An ETH\-based lower bound for size\-two lists interpolation](https://arxiv.org/html/2607.25973#S4.SS4) 5. [4\.5Reflection time](https://arxiv.org/html/2607.25973#S4.SS5)
5. [5The general algorithm](https://arxiv.org/html/2607.25973#S5)1. [5\.1The fixed\-palette list\-to\-list bootstrap](https://arxiv.org/html/2607.25973#S5.SS1)
6. [6Plucking up the courage to specify the constants](https://arxiv.org/html/2607.25973#S6)1. [6\.1The seed solver](https://arxiv.org/html/2607.25973#S6.SS1) 2. [6\.2One bootstrap step](https://arxiv.org/html/2607.25973#S6.SS2) 3. [6\.3Iterating over all list sizes](https://arxiv.org/html/2607.25973#S6.SS3)
7. [7Discussion and open problems](https://arxiv.org/html/2607.25973#S7)
8. [References](https://arxiv.org/html/2607.25973#bib)
9. [AAI Storytime](https://arxiv.org/html/2607.25973#A1)

## 1Introduction

The problem ofkk\-coloring a graph, or determining its*chromatic number*is one of the most fundamental and well\-studied NP\-complete problems\. It was already listed as one of the first NP\-complete problems in Karp’s seminal 1972 paper\[[KAR72](https://arxiv.org/html/2607.25973#bib.bib33)\]\. Similarly tokk\-SAT, the problem of22\-coloring is polynomial, yetkk\-coloring is NP\-complete for everyk≥3k\\geq 3\[[LOV73](https://arxiv.org/html/2607.25973#bib.bib34),[STO73](https://arxiv.org/html/2607.25973#bib.bib35)\]\.

There is substantial work exploring exponential\-time worst\-case algorithms for NP\-Complete problems\. A 2003 survey of Woeginger\[[WOE03](https://arxiv.org/html/2607.25973#bib.bib37)\]covers and refers to dozens of papers exploring such algorithms for many problems including satisfiability, graph coloring, knapsack, TSP, maximum independent sets and more\. A subsequent survey of Fomin and Kaski\[[FK13](https://arxiv.org/html/2607.25973#bib.bib43)\]and a book of Fomin and Kratsch\[[FK10](https://arxiv.org/html/2607.25973#bib.bib44)\]further cover the topic\. More recently, the study of these exact running times has become closely connected with*fine\-grained complexity*\. Rather than distinguishing only between polynomial and superpolynomial running times, fine\-grained complexity supplements qualitative assumptions such asP≠NP\\mathrm\{P\}\\neq\\mathrm\{NP\}with quantitative hypotheses asserting that particular benchmark problems cannot be solved substantially faster than their best known algorithms\[[IP01](https://arxiv.org/html/2607.25973#bib.bib13),[IPZ01](https://arxiv.org/html/2607.25973#bib.bib45),[CDL\+16](https://arxiv.org/html/2607.25973#bib.bib46),[WW18](https://arxiv.org/html/2607.25973#bib.bib47),[AW14](https://arxiv.org/html/2607.25973#bib.bib48),[BI15](https://arxiv.org/html/2607.25973#bib.bib49),[BRI14](https://arxiv.org/html/2607.25973#bib.bib50),[WIL18](https://arxiv.org/html/2607.25973#bib.bib51)\]\.

For SAT, the straightforward enumeration algorithm runs inO∗​\(2n\)O^\{\*\}\(2^\{n\}\)time\. On the other hand, it is known that for every fixedkkthere exists a constantεk\>0\\varepsilon\_\{k\}\>0such thatkk\-SAT can be solved inO∗​\(\(2−εk\)n\)O^\{\*\}\\left\(\\left\(2\-\\varepsilon\_\{k\}\\right\)^\{n\}\\right\)time\. This was first shown by Monien and Speckenmeyer in 1985\[[MS85](https://arxiv.org/html/2607.25973#bib.bib14)\]\. Since then a long list of improvements for theseεk\\varepsilon\_\{k\}values have been published\[[ROD96](https://arxiv.org/html/2607.25973#bib.bib20),[PPZ99](https://arxiv.org/html/2607.25973#bib.bib15),[PPS\+05](https://arxiv.org/html/2607.25973#bib.bib17),[SCH99](https://arxiv.org/html/2607.25973#bib.bib10),[HER14b](https://arxiv.org/html/2607.25973#bib.bib11),[HER14a](https://arxiv.org/html/2607.25973#bib.bib12),[SS17](https://arxiv.org/html/2607.25973#bib.bib21),[HKZ\+19](https://arxiv.org/html/2607.25973#bib.bib22)\]\. Several of the most popular among the aforementioned fine\-grained conjectures focus on the asymptotic behavior of theseεk\\varepsilon\_\{k\}values\[[IP01](https://arxiv.org/html/2607.25973#bib.bib13),[IPZ01](https://arxiv.org/html/2607.25973#bib.bib45),[VW21](https://arxiv.org/html/2607.25973#bib.bib52)\]\.

The coloring problem is less well understood\. The naive enumeration algorithm forkk\-coloring takesO∗​\(kn\)O^\{\*\}\(k^\{n\}\)time\. Thus, at a first glance it is not even clear that computing the chromatic number takes “only” exponential time\. Nonetheless, a simple dynamic\-program computes the chromatic number inO∗​\(3n\)O^\{\*\}\(3^\{n\}\)time\[[LAW76](https://arxiv.org/html/2607.25973#bib.bib32)\]\. More sophisticated algorithms followed\[[MM65](https://arxiv.org/html/2607.25973#bib.bib39),[PU59](https://arxiv.org/html/2607.25973#bib.bib40),[EPP01](https://arxiv.org/html/2607.25973#bib.bib41),[BYS04](https://arxiv.org/html/2607.25973#bib.bib38)\], until their culmination with a chromatic number algorithm running inO∗​\(2n\)O^\{\*\}\(2^\{n\}\)time by Björklund, Husfeldt and Koivisto in 2006\[[BHK09](https://arxiv.org/html/2607.25973#bib.bib4)\]\.

Fork=3,4k=3,4, faster algorithms are known for thekk\-coloring problem, as well as for more general problems such askk\-list\-coloring and even general\(k,2\)\(k,2\)\-CSPs\. Schiermeyer\[[SCH93](https://arxiv.org/html/2607.25973#bib.bib42)\]showed that33\-coloring can be solved inO∗​\(1\.415n\)O^\{\*\}\(1\.415^\{n\}\)time\. Beigel and Eppstein\[[BE05](https://arxiv.org/html/2607.25973#bib.bib2)\]gave algorithms solving33\-coloring inO∗​\(1\.3289n\)O^\{\*\}\(1\.3289^\{n\}\)time and44\-coloring inO∗​\(1\.8072n\)O^\{\*\}\(1\.8072^\{n\}\)time in 2005\. These numbers were later improved\[[FGS07](https://arxiv.org/html/2607.25973#bib.bib25),[WGJ\+24](https://arxiv.org/html/2607.25973#bib.bib57),[MEI23](https://arxiv.org/html/2607.25973#bib.bib58)\]\. In\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]these were extended to algorithms for55\-coloring and66\-coloring running in\(2−ε\)n\(2\-\\varepsilon\)^\{n\}time, for someε\>0\\varepsilon\>0, as well\. Unlikekk\-SAT, though, for everyk\>6k\>6the best known running time forkk\-coloring remainedO∗​\(2n\)O^\{\*\}\(2^\{n\}\), the same as generally computing the chromatic number\.

In this work, we fully resolve this long\-standing gap by showing an algorithm with an improved exponent base for every fixed number of colors\.

###### Theorem\.

For everyk∈ℕk\\in\\mathbb\{N\}there existsεk\>0\\varepsilon\_\{k\}\>0such thatkk\-coloring can be solved in\(2−εk\)n\(2\-\\varepsilon\_\{k\}\)^\{n\}with a randomized algorithm\.

The proof establishes the result in the equivalent but more flexible language of*List Coloring*over a fixed palette\. In the list coloring problem, we are given a graphGGand listsL​\(v\)L\(v\)of possible colors for each vertexv∈V​\(G\)v\\in V\(G\), we are asked to find a proper coloring ofGGsuch that each vertexvvis colored by some color fromL​\(v\)L\(v\)\. In thekk\-list\-coloring problem each listL​\(v\)L\(v\)is of size at mostkk\. The setP=∪vL​\(v\)P=\\cup\_\{v\}L\(v\)of all possible colors is called*the palette*\. Note thatkk\-coloring is a special case ofkk\-list\-coloring over the palette\[k\]\[k\]in which∀v\.L​\(v\)=\[k\]\\forall v\.L\(v\)=\[k\]\. TheO∗​\(2n\)O^\{\*\}\(2^\{n\}\)algorithm of\[[BHK09](https://arxiv.org/html/2607.25973#bib.bib4)\]works also for list coloring\.

For our proof, it is useful to work in the language of list coloring over a fixed palette\. We show that for every fixed palette sizeK=\|P\|K=\|P\|, list coloring over the palettePPadmits an algorithm with an improved exponent base\.

###### Theorem\.

For everyK∈ℕK\\in\\mathbb\{N\}there existsεK\>0\\varepsilon\_\{K\}\>0such that list\-coloring over a palettePPof sizeKKcan be solved in\(2−εK\)n\(2\-\\varepsilon\_\{K\}\)^\{n\}with a randomized algorithm\.

We prove the result by bringing together two complementary lines of work: the reduction from\(k\+2\)\(k\+2\)\-coloring tokk\-list coloring developed in\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\], and the hypergraph\-container framework introduced in\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]\. The key new idea we introduce is to strengthen the former reduction so that, rather than merely shortening many color lists, it produces two large sets of vertices whose lists are supported on complementary sub\-palettes\. Then, we develop new algorithms for instances mixing long and short lists that provide the motivating special case, while the Extensions\-Sum machinery from the latter work allows the two supported parts to be combined in sub\-2n2^\{n\}time\. This yields an iterable bootstrap: over any fixed palette, a sub\-2n2^\{n\}algorithm forkk\-list\-coloring implies one for\(k\+1\)\(k\+1\)\-list\-coloring\. Starting from polynomial\-time22\-list\-coloring and applying the bootstrap successively gives a\(2−εK\)n\(2\-\\varepsilon\_\{K\}\)^\{n\}time algorithm for every fixed palette sizeKK\.

#### Other related works\.

Algorithms forkk\-coloring with sub\-2n2^\{n\}running times were developed for several restricted graph families, such as bounded\-degree graphs\[[BHK\+10](https://arxiv.org/html/2607.25973#bib.bib53)\], sparse graphs\[[GKM16](https://arxiv.org/html/2607.25973#bib.bib24)\], graphs with many low\-degree vertices\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\], and almost\-regular graphs\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]\.

Recently, Björklund, Curticapean, Husfeldt, Kaski, and Pratt showed that if Strassen’s generalized asymptotic rank conjecture holds, then a deterministicO∗​\(1\.99982n\)O^\{\*\}\(1\.99982^\{n\}\)\-time algorithm for computing the chromatic number exists\[[BCH\+25](https://arxiv.org/html/2607.25973#bib.bib54)\]\. This is a very strong and non\-constructive conjecture \(which even in its weaker form implies that matrix multiplication admits ann2\+o​\(1\)n^\{2\+o\(1\)\}time algorithm\)\. This conjecture is also known to be incompatible with the Set Cover conjecture\[[BK24](https://arxiv.org/html/2607.25973#bib.bib55),[PRA24](https://arxiv.org/html/2607.25973#bib.bib56)\]\. Thus, the above may be interpreted as further evidence against the conjecture rather than as a conditional improved coloring algorithm, depending on the reader’s beliefs\.

## 2Overview

Our proof builds on the reduction framework introduced in\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]\. The main structural tool there is that, for every fixedα,Δ\>0\\alpha,\\Delta\>0, List Coloring admits a sub\-2n2^\{n\}algorithm whenever at leastα​n\\alpha nvertices have degree at mostΔ\\Delta\. Consequently, after arbitrarily choosing the constants, we may focus on graphs in which almost every vertex has large degree\.

In such a graph, we may sample a small random set of vertices and color them naively \(say, by enumerating over all options\)\. That small set sees much of the graph as its neighbors, due to their high degrees\. In particular, for any color that occurs many times in the neighborhood of a vertex, the random set is likely to contain a neighbor with that color, which in turn deletes this option from the vertex’s list \(assuming we colored the small sampled set correctly\)\. We refer to that as the*easy solver*used throughout the paper\.

This reasoning gave the two reductions of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]: a sub\-2n2^\{n\}algorithm forkk\-list\-coloring implies such an algorithm for both\(k\+1\)\(k\+1\)\-coloring and\(k\+2\)\(k\+2\)\-coloring\. The first is immediate from the above: the easy solver gets rid of at least one color for each vertex, reducing the list of color options per vertex by one\. The second reduction already encounters an important obstruction\. Repeatedly hitting the neighborhood of a high\-degree vertex need not reveal several colors: almost all of its neighbors may receive the same color in a fixed coloring\. That failure case is nevertheless useful: if a vertex has many neighbors but nearly all of them are of the same color, then we may sample a subset of its neighbors and then guess they all receive one common color and contract them\. The resulting reduction, together with the previously known algorithms for44\-list\-coloring, gave the first sub\-2n2^\{n\}algorithms for55\- and66\-coloring\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7),[BE05](https://arxiv.org/html/2607.25973#bib.bib2)\]\.

The first new obstacle appears when extending the argument to\(k\+3\)\(k\+3\)\-coloring\. The neighborhood of a high\-degree vertex may now be concentrated on two colors rather than one\. A similar reduction then does not allow us to guess many of a vertex’s neighbors are of identical color \- but instead, that they must be colored with one of two specific colors\. Thus, we can produce many vertices with shortened lists of size two\. Treating their two possible colors by direct branching would lead to the usual2n2^\{n\}bound and thus consume precisely the saving we hope to obtain\. On the other hand, if all vertices had lists of size two, then this would be an instance of22\-list\-coloring or22\-SAT which is polynomial time solvable\. This leads us to isolate a binary\-list interpolation problem: how much faster does list\-coloring become when a linear number of vertices have lists of size two?

We solve this problem by grouping vertices that share the same two\-element list and separating the use of these two colors from the remaining colors\. The resulting algorithm runs inO∗​\(2n−b/\(K2\)\)O^\{\*\}\(2^\{n\-b/\\binom\{K\}\{2\}\}\)time whenbbvertices have lists of size at most two over a palette of sizeKK\. This interpolation between polynomial\-time22\-list\-coloring and general list\-coloring supplies exactly the additional saving needed for the three\-step reduction\.

This interpolation algorithm is particularly simple and is stated in a self\-contained manner\. Supposebbvertices have lists of size at most two\. Ignoring technical details such as singleton lists, some pairQ⊆PQ\\subseteq Pis the list of at leastb/\(K2\)b/\\binom\{K\}\{2\}vertices; remove this most frequent pair class and call the remaining vertex setHH\. Using an algorithm of\[[BHK\+07](https://arxiv.org/html/2607.25973#bib.bib3),[BHK09](https://arxiv.org/html/2607.25973#bib.bib4)\]that decides for each induced subgraph whether it is colorable in the sameO∗​\(2n\)O^\{\*\}\(2^\{n\}\)time needed for solving coloring on the entire graph, we determine simultaneously whichX⊆HX\\subseteq Hare colorable using only colors outsideQQ\. For each suchXX, the complement is restricted to the two colors ofQQand is therefore solved by22\-SAT in polynomial time\. The two parts of the colorings combine without any compatibility check as they are on disjoint sets of colors\. The running time is

O∗​\(2n−b/\(K2\)\)=O∗​\(2n−b​qKb\),qK=21−1/\(K2\)<2\.O^\{\*\}\\\!\\left\(2^\{\\,n\-b/\\binom\{K\}\{2\}\}\\right\)=O^\{\*\}\\\!\\left\(2^\{n\-b\}q\_\{K\}^\{b\}\\right\),\\qquad q\_\{K\}=2^\{\\,1\-1/\\binom\{K\}\{2\}\}<2\.Together with the previous gap\-two reduction this yields a sub\-2n2^\{n\}algorithm for\(k\+3\)\(k\+3\)\-coloring from one forkk\-list\-coloring\. In particular, the44\-list\-coloring algorithm of\[[BE05](https://arxiv.org/html/2607.25973#bib.bib2)\]gives the first such algorithm for77\-coloring\.

The interpolation theorem also isolates a useful limitation of this argument\. The tempting endpointq=1q=1, under which binary\-list vertices would contribute no exponential cost, is impossible assuming ETH: We construct a reduction from Traxler’s bounded\-frequency\(d,2\)\(d,2\)\-CSP lower bound\[[TRA08](https://arxiv.org/html/2607.25973#bib.bib5)\], by showing that such CSPs can be encoded as list\-coloring instances in which most lists are of size two\. On the other hand, we do not rule out a palette\-independent constant1<q<21<q<2\. This appears to be the main obstacle between the fixed\-palette result proved here and the still\-open problem ofkk\-list\-coloring over an arbitrarily large palette\.

For the general reduction, the three\-step warm\-up appears insufficient: Binary lists have a polynomial\-time endpoint, but there is no analogous reason that an instance containing many lists of size three or four should be easier than a general instance\. For the full generalization then we combine the sampling reduction and the terminal algorithm instead of generalizing either one in isolation\.

Consider one step of this recursive reduction: we assume a sub\-2n2^\{n\}algorithm for\(k−1\)\(k\-1\)\-list\-coloring over the fixed paletteP=\[K\]P=\[K\], and aim to solvekk\-list\-coloring over the same palette\. Unless the easy solver already applies, there are linearly many high\-degree vertices whose lists have size exactlykk, but whose neighborhoods do not contain any one sufficiently frequent color\. Since the palette is fixed, there are only constantly many possibilities for the complementsP∖L​\(v\)P\\setminus L\(v\)of these lists\. We may therefore restrict attention to a linear set of vertices sharing one common complementQQ, and write

All the retained vertices have list exactlyRR, and are therefore forbidden from using any color inQQ\.

We now repeatedly select vertices from this retainedRR\-side and restrict small random sets of their neighbors to colors inQQ\. A successful sequence of such steps preserves a linear number of the original vertices whose lists are contained inRR, while creating a second linear set of vertices whose lists are contained inQQ\. Thus, rather than merely producing many vertices with somewhat shorter lists, the reduction produces two sets with opposite palette restrictions:

𝒜Q=\{v:L​\(v\)⊆Q\},ℬR=\{v:L​\(v\)⊆R\}\.\\mathcal\{A\}\_\{Q\}=\\\{v:L\(v\)\\subseteq Q\\\},\\qquad\\mathcal\{B\}\_\{R\}=\\\{v:L\(v\)\\subseteq R\\\}\.This is the general structure replacing the size\-two lists used in the warm\-up\.

It remains to exploit these two sets algorithmically\. Every vertex eventually colored fromQQmust lie outsideℬR\\mathcal\{B\}\_\{R\}, while every vertex colored fromRRmust lie outside𝒜Q\\mathcal\{A\}\_\{Q\}\. Hence we know two large, generally overlapping, supersets containing the two parts of the eventual coloring\. The difficulty is to determine how the vertices in their overlap should be divided between the two palettes, and then to combine the resulting colorings\. In the binary interpolation algorithm this combination was particularly simple, because one side was solved by22\-SAT\. For larger setsQQ, no such argument is available\.

Fortunately, the Extensions\-Sum machinery developed in\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]for the graph\-container approach solves exactly this more general combination problem\. One of its main consequences is that an instance with the two supported sets above can be solved in

O∗​\(2n−\|𝒜Q\|\+2n−\|ℬR\|\)O^\{\*\}\\\!\\left\(2^\{\\,n\-\|\\mathcal\{A\}\_\{Q\}\|\}\+2^\{\\,n\-\|\\mathcal\{B\}\_\{R\}\|\}\\right\)time\. Informally, this is comparable to enumerating separately over the possibleQQ\-colored part and the possibleRR\-colored part, despite the fact that their allowed vertex sets overlap\. Both supported sets constructed by the reduction have linear size, so the terminal algorithm is faster than2n2^\{n\}\.

Of course, many details are swept under the rug in this high\-level overview\. In particular, the algorithm of course has no access to the eventual coloring and we thus cannot tell which vertices have many neighbors colored by colors from their lists and which do not\. The full algorithm solves this by making a sequence of randomized guesses and setting the parameters in a way that guarantees the benefit from succeeding in such a guess outweighs the probability of failing in it\.

Thus, we end up with a reduction from list\-coloring to list\-coloring \(rather than the previous reductions from*coloring*to list\-coloring\),

\(k−1\)​\-list\-coloring over​P⟹k​\-list\-coloring over​P\(k\-1\)\\text\{\-list\-coloring over \}P\\quad\\Longrightarrow\\quad k\\text\{\-list\-coloring over \}Pwith a sub\-2n2^\{n\}running time for every3≤k≤K3\\leq k\\leq K\. This reduction can then be bootstrapped to construct sub\-2n2^\{n\}algorithms for everykk\.

### 2\.1Organization and reading guide

Section[3](https://arxiv.org/html/2607.25973#S3)collects the black\-box ingredients and the elementary reductions used later: normalization and decision\-to\-search, the simultaneous coloring of all induced list sub\-instances of\[[BHK\+07](https://arxiv.org/html/2607.25973#bib.bib3)\], the bounded\-degree theorem of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\], and the two\-block consequence of Extensions\-Sum from\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]\. Section[4](https://arxiv.org/html/2607.25973#S4)proves the three\-step warm\-up reduction, develops useful tools to be later used in the general reduction, gives the binary\-list interpolation algorithm, and establishes its ETH\-based limitation\. This section is also intended to motivate all of the objects in the general proof\. Section[5](https://arxiv.org/html/2607.25973#S5)proves the fixed\-palette list\-to\-list bootstrap and then iterates it to obtain the main theorem\. In Section[6](https://arxiv.org/html/2607.25973#S6)we informally repeat the proof with some tedious bookkeeping to understand the asymptotic behavior of the quantitative constants our algorithm achieves; it is not necessary for proving any of our results but meant to be used as a baseline for future quantitative improvements\. Section[7](https://arxiv.org/html/2607.25973#S7)is finally used for discussion and listing the remaining open problems\.

## 3Background

The terminology used throughout the paper is standard\. For a graphGGwe denote byV​\(G\)V\(G\)andE​\(G\)E\(G\)its vertex\-set and edge\-set, respectively\. Throughout the paper,nnis used to denote\|V​\(G\)\|\|V\(G\)\|\. For a subsetV′⊆V​\(G\)V^\{\\prime\}\\subseteq V\(G\)we denote byG​\[V′\]G\[V^\{\\prime\}\]the sub\-graph ofGGinduced byV′V^\{\\prime\}\. Forv∈Vv\\in Vwe denote bydeg⁡\(v\)\\deg\(v\)the degree ofvvinGG, byN​\(v\)N\(v\)the set of neighbors ofvv, and byN​\[v\]:=N​\(v\)∪\{v\}N\[v\]:=N\(v\)\\cup\\\{v\\\}\. All logarithms are base two\.

The notationO∗​\(⋅\)O^\{\*\}\(\\cdot\)suppresses factors polynomial in the input size; throughout the algorithmic proof,PPand all displayed sampling parameters are fixed constants\. We allow all algorithms to have an exponentially small error\-probability\. We remark that as the output of coloring algorithms is verifiable, all errors can be assumed to be one\-sided\.

### 3\.1Coloring, List Coloring, and Constraint Satisfaction Problems

In the*kk\-coloring problem*, we are given a graphGGand need to decide whether there exists akk\-coloringc:V​\(G\)→\[k\]c:V\(G\)\\rightarrow\[k\]ofGG, such that for every\(u,v\)∈E​\(G\)\(u,v\)\\in E\(G\)we havec​\(u\)≠c​\(v\)c\(u\)\\neq c\(v\)\. If a graph has akk\-coloring, we say that it iskk\-colorable\. In the*chromatic number problem*, we are given a graphGGand need to computeχ​\(G\)\\chi\(G\), the minimal integerkkfor whichGGiskk\-colorable\.

For a*palette*PP, which we would usually take to beP=\[K\]P=\[K\]for some integerKK, a list\-coloring instance \(overPP\) is a graphGGwith a nonempty listL​\(v\)⊆PL\(v\)\\subseteq Pat each vertex\. A list coloring is a mapc:V​\(G\)→Pc:V\(G\)\\to Psatisfyingc​\(v\)∈L​\(v\)c\(v\)\\in L\(v\)andc​\(u\)≠c​\(v\)c\(u\)\\neq c\(v\)on every edge\(u,v\)∈E​\(G\)\(u,v\)\\in E\(G\)\. In thekk\-list\-coloring problem \(overPP\) all lists have size at mostkk\.

In a general\(a,b\)\(a,b\)\-CSP \(Constraint Satisfaction Problem, see\[[KUM92](https://arxiv.org/html/2607.25973#bib.bib9)\]or\[[SCH99](https://arxiv.org/html/2607.25973#bib.bib10)\]for a complete definition and discussions\) we are given a list of*constraints*on the values of subsets of sizebbofnndistinctaa\-ary variables, and need to decide whether there exists an assignment of values to the variables for which all constraints are satisfied\. A general constraint on a setx1,…,xbx\_\{1\},\\ldots,x\_\{b\}ofaa\-ary variables is a subsetTTof theaba^\{b\}possible assignments in\{x1,…​xb\}→\[a\]\\\{x\_\{1\},\\ldots x\_\{b\}\\\}\\rightarrow\[a\]\. The constraint is satisfied by an assignmentcc, possibly on more variables, if the restriction ofccto\{x1,…​xb\}\{\\\{x\_\{1\},\\ldots x\_\{b\}\\\}\}is inTT\. Whenb=2b=2, that is, every constraint is on a pair of variables, then without loss of generality all constraints are of the form “c​\(x1\)≠c1∨c​\(x2\)≠c2c\(x\_\{1\}\)\\neq c\_\{1\}\\;\\vee\\;c\(x\_\{2\}\)\\neq c\_\{2\}” for variablesx1,x2x\_\{1\},x\_\{2\}and colorsc1,c2c\_\{1\},c\_\{2\}\.

Every instance ofkk\-coloring is also an instance ofkk\-list\-coloring \(over paletteP=\[k\]P=\[k\]\)\. Furthermore, every instance ofkk\-list\-coloring, irrespective of the palette size, is also a\(k,2\)\(k,2\)\-CSP\. Not to be confused withkk\-SAT, on the other hand, which is an example of a\(2,k\)\(2,k\)\-CSP\.

Bothkk\-coloring andkk\-list\-coloring can be described as set\-partition problems \(e\.g\., “Can the entire vertex setV​\(G\)V\(G\)be covered bykkindependent sets inGG?”\); this reformulation is crucial to theO∗​\(2n\)O^\{\*\}\(2^\{n\}\)algorithm solving them both, independently of the value ofkk\[[BHK09](https://arxiv.org/html/2607.25973#bib.bib4)\]\. The more general\(k,2\)\(k,2\)\-CSP problem though, does not have such a formulation, and indeed Traxler\[[TRA08](https://arxiv.org/html/2607.25973#bib.bib5)\]proved that if the Exponential Time Hypothesis \(ETH\) holds, then there exists a constantα\>0\\alpha\>0such that\(k,2\)\(k,2\)\-CSP requireskα​nk^\{\\alpha n\}time\.

### 3\.2From deciding colorability to finding a coloring

The algorithms in this paper are phrased primarily as decision algorithms: they determine whether a given graph or list instance is colorable\. This does not prevent us from returning an explicit coloring\. For ordinarykk\-coloring, a standard self\-reduction converts any decision algorithm into a search algorithm with only polynomial overhead; e\.g\., see Lemma 2\.2 of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]\. That reduction repeatedly adds nonedges whose addition preserveskk\-colorability, until the resulting graph is edge\-maximalkk\-colorable, which is simply the complement of a disjoint union of cliques, and its color classes can thus be read off directly\.

In the list\-coloring setting used here, there is a simpler self\-reduction that does not alter the graph and only shrinks lists\. It therefore preserves the fixed palette, the maximum list size, all degree conditions, and every other promise on the underlying graph\.

###### Lemma 3\.1\(Decision\-to\-search for List Coloring\)\.

Fix a palettePP\. Suppose that list\-coloring overPPof annn\-vertex instance can be decided in timeT​\(n\)T\(n\)\. Then, whenever the instance is colorable, an explicit list coloring can be found in

O∗​\(T​\(n\)\)O^\{\*\}\\bigl\(T\(n\)\\bigr\)time\.

###### Proof\.

Maintain a list assignmentL′L^\{\\prime\}for which the current instance is known to be colorable, initiallyL′=LL^\{\\prime\}=L\. Process the vertices one at a time\. At a vertexvv, for everyc∈L′​\(v\)c\\in L^\{\\prime\}\(v\), query the decision algorithm on the instance obtained by replacingL′​\(v\)L^\{\\prime\}\(v\)with the singleton\{c\}\\\{c\\\}\. At least one such restriction is colorable, so an exact decision algorithm identifies a color that may be fixed atvv\. After all vertices have been processed, every list is a singleton and these singleton colors form the required coloring\. ∎

Consequently, throughout the paper we may present only the decision version of each algorithm\. Whenever an explicit coloring is needed, we apply Lemma[3\.1](https://arxiv.org/html/2607.25973#S3.Thmtheorem1)\. Notice also that singleton restrictions never enlarge a list or expand the color palette\.

### 3\.3Normalization of list\-coloring instances

We use the following elementary normalization\.

###### Lemma 3\.2\(Normalization\)\.

Let\(G,L\)\(G,L\)be a list\-coloring instance\.

1. \(i\)Deleting an edge\(u,v\)\(u,v\)withL​\(u\)∩L​\(v\)=∅L\(u\)\\cap L\(v\)=\\varnothingpreserves exactly the set of list colorings\. We denote by*\(N\)*the process of repeating this operation as long as such an edge exists\.
2. \(ii\)Repeatedly fixing a singletonL​\(v\)=\{c\}L\(v\)=\\\{c\\\}, deletingvv, and deletingccfrom all neighboring lists either produces an empty list, certifying infeasibility, or produces in polynomial time an equivalent residual instance with no singleton lists\. A coloring of the residual instance extends uniquely to a complete coloring ofGG\.

Neither operation enlarges a list\.

###### Proof\.

For \(i\), endpoints whose lists are disjoint can never be assigned the same color, so their edge imposes no constraint\. For \(ii\), every feasible coloring must assignvvthe unique colorcc; properness then forbidsccat each neighbor\. Thus one propagation step is an equivalence, and induction proves the claim for the entire sequence\. At least one vertex is deleted at each step, so the procedure is polynomial\. Reversing these assignments reconstructs a coloring of the original instance\. Because subsequent operations only shrink lists, the endpoints of every edge deleted by \(N\) remain disjoint\. ∎

In the warm\-up we use both parts and call this*full normalization*\. The general proof in Section[5](https://arxiv.org/html/2607.25973#S5)deliberately uses only rule \(N\)\.

### 3\.4Coloring all induced subinstances for the price of one

The following list\-coloring extension of a result by Björklund, Husfeldt, Kaski, and Koivisto\[[BHK\+07](https://arxiv.org/html/2607.25973#bib.bib3)\]will be used in the binary interpolation argument\. In\[[BHK\+07](https://arxiv.org/html/2607.25973#bib.bib3)\], the authors show that a simple modification of theO∗​\(2n\)O^\{\*\}\(2^\{n\}\)time graph algorithm of\[[BHK09](https://arxiv.org/html/2607.25973#bib.bib4)\]gives similar running time to find allkk\-colorable induced subgraphs of a given graph\. While not explicitly written in their work, the same modification extends in a straightforward manner to theO∗​\(2n\)O^\{\*\}\(2^\{n\}\)list\-coloring algorithm from\[[BHK09](https://arxiv.org/html/2607.25973#bib.bib4)\]\. We include, briefly, this extension here for completeness\.

###### Lemma 3\.3\(All induced list subinstances\)\.

Fix a palettePP\. Given an instance of list\-coloring on a graphGGwith lists contained inPP, one can determine simultaneously, for everyX⊆V​\(G\)X\\subseteq V\(G\), whetherG​\[X\]G\[X\]is list colorable, inO∗​\(2\|V​\(G\)\|\)O^\{\*\}\(2^\{\|V\(G\)\|\}\)time\.

###### Proof\.

For eachc∈Pc\\in P, define a function on subsets ofV​\(G\)V\(G\)by

fc​\(S\)=1⟺S​is independent and​c∈L​\(v\)​for every​v∈S\.f\_\{c\}\(S\)=1\\quad\\Longleftrightarrow\\quad S\\text\{ is independent and \}c\\in L\(v\)\\text\{ for every \}v\\in S\.We takefc​\(∅\)=1f\_\{c\}\(\\varnothing\)=1, so a color class may be unused\. Every explicit tablefc​\(⋅\)f\_\{c\}\(\\cdot\)is easily filled inO∗​\(2\|V​\(G\)\|\)O^\{\*\}\(2^\{\|V\(G\)\|\}\)time\. The iterated disjoint subset convolution

F=∗c∈PfcF=\*\_\{c\\in P\}f\_\{c\}counts, for everyXX, ordered partitions ofXXinto allowed independent color classes\. ThusF​\(X\)\>0F\(X\)\>0exactly whenG​\[X\]G\[X\]is list colorable\. The fast subset convolution of\[[BHK\+07](https://arxiv.org/html/2607.25973#bib.bib3)\]computes all values of the convolution inO∗​\(2\|V​\(G\)\|\)O^\{\*\}\(2^\{\|V\(G\)\|\}\)arithmetic operations because\|P\|\|P\|is fixed\. The counts are at most\|P\|\|V​\(G\)\|\|P\|^\{\|V\(G\)\|\}, so their bit lengths are polynomial\. ∎

The ordinary\-coloring version of Lemma[3\.3](https://arxiv.org/html/2607.25973#S3.Thmtheorem3)is stated explicitly in\[[BHK\+07](https://arxiv.org/html/2607.25973#bib.bib3), Section 4\.3\]: they observe that computingf∗k​\(S\)f^\{\*k\}\(S\)for everyS⊆V​\(G\)S\\subseteq V\(G\)finds allkk\-colorable induced subgraphs inO∗​\(2\|V​\(G\)\|\)O^\{\*\}\(2^\{\|V\(G\)\|\}\)total time\. The minor extension here is to use a different functionfcf\_\{c\}for each color, thereby encoding the vertex lists\.

### 3\.5Main tool I: Coloring with bounded\-degrees

The first of the main tools we use from previous works is a theorem from\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\], which shows that coloring and list\-coloring can be solved in sub\-2n2^\{n\}time whenever the graph has at least \(any\) constant fraction of vertices whose degrees are bounded by \(any\) constant\.

###### Definition 3\.4\.

Forα∈\[0,1\]\\alpha\\in\[0,1\]andΔ≥0\\Delta\\geq 0, a graph is\(α,Δ\)\(\\alpha,\\Delta\)\-bounded if at leastα​\|V​\(G\)\|\\alpha\|V\(G\)\|of its vertices have degree at mostΔ\\Delta\.

We cite the following theorem\. Note that it is phrased for list\-coloring and permits an arbitrary color palette\.

###### Theorem 3\.5\(\(α,Δ\)\(\\alpha,\\Delta\)\-bounded List Coloring, Theorem 1\.3 of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]\)\.

For every fixedk,α,Δ\>0k,\\alpha,\\Delta\>0, there is a constantCk,α,Δ<2C\_\{k,\\alpha,\\Delta\}<2such thatkk\-list\-coloring on annn\-vertex\(α,Δ\)\(\\alpha,\\Delta\)\-bounded graph can be solved in

O∗​\(Ck,α,Δn\)O^\{\*\}\\bigl\(C\_\{k,\\alpha,\\Delta\}^\{n\}\\bigr\)time, regardless of the size of the color palettePP\.

We use this theorem as\-stated without modifications\. We remark that this Theorem was derived via the introduction of a certain combinatorial subset removal lemma, which results in the advantage\(2−Ck,α,Δ\)\\left\(2\-C\_\{k,\\alpha,\\Delta\}\\right\)having a rather bad dependence on the parametersk,α,Δk,\\alpha,\\Delta; we go back to discuss these explicit constants in Section[6](https://arxiv.org/html/2607.25973#S6)\.

Theorem[3\.5](https://arxiv.org/html/2607.25973#S3.Thmtheorem5)was used in\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]to construct reductions from\(k\+1\)\(k\+1\)and\(k\+2\)\(k\+2\)\-coloring tokk\-list\-coloring\. In combination with the sub\-2n2^\{n\}algorithms for3,43,4\-list\-coloring \(and in fact, even for\(4,2\)\(4,2\)\-CSPs\) of\[[BE05](https://arxiv.org/html/2607.25973#bib.bib2)\]this resulted in the first sub\-2n2^\{n\}algorithms for5,65,6\-coloring\.

###### Theorem 3\.6\(Theorems 1\.4 and 1\.5 of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]\)\.

Letkkbe a fixed integer\. For everyδ\>0\\delta\>0there is aδ′\>0\\delta^\{\\prime\}\>0such that the following hold\.

1. \(i\)If\(k−1\)\(k\-1\)\-list\-coloring is solvable inO∗​\(\(2−δ\)n\)O^\{\*\}\(\(2\-\\delta\)^\{n\}\)time, thenkk\-coloring is solvable inO∗​\(\(2−δ′\)n\)O^\{\*\}\(\(2\-\\delta^\{\\prime\}\)^\{n\}\)time; this reduction is deterministic\.
2. \(ii\)If\(k−2\)\(k\-2\)\-list\-coloring is solvable inO∗​\(\(2−δ\)n\)O^\{\*\}\(\(2\-\\delta\)^\{n\}\)time, thenkk\-coloring is solvable with exponentially small one\-sided error inO∗​\(\(2−δ′\)n\)O^\{\*\}\(\(2\-\\delta^\{\\prime\}\)^\{n\}\)\.

### 3\.6Main tool II: Two\-block color restrictions and Extensions\-Sum

The second external tool comes from the partition\-container framework of\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]\. That work introduced algorithmic applications of the hypergraph container method, as well as a problem called Extensions\-Sum in order to turn structural information supplied by graph containers into savings in inclusion\-exclusion algorithms\. A container may restrict an individual color class \(corresponding to an independent set\) to a proper subset of the vertices, but the usual inclusion\-exclusion formula still contains2n2^\{n\}terms\. Extensions\-Sum was introduced to exploit the fact that the contribution associated with a color depends only on its allowed vertex set\.

More precisely, suppose that every colorccin a fixed palettePPis assigned an allowed domainVc⊆V​\(G\)V\_\{c\}\\subseteq V\(G\), and we ask for a proper coloringφ\\varphisatisfying

φ​\(v\)=c⟹v∈Vc\.\\varphi\(v\)=c\\quad\\Longrightarrow\\quad v\\in V\_\{c\}\.This is exactly a list\-coloring \(over palettePP\) instance under the additional restrictions

L​\(v\)⊆\{c∈P:v∈Vc\}\.L\(v\)\\subseteq\\\{c\\in P:v\\in V\_\{c\}\\\}\.Lemma 3\.14 of\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]expresses the relevant inclusion\-exclusion computation as an Extensions\-Sum instance, while Lemma 3\.11 constructs its input tables\. Observation 3\.23 shows that colors whose domains have small union may be merged into a single Extensions\-Sum function, and Lemma 3\.16 evaluates the resulting two\-function instance in time equal, up to polynomial factors, to the sum of the two table sizes\. Together, these results give the following black\-box statement\.

###### Theorem 3\.7\(Two\-block restricted coloring\)\.

LetP=Q∪˙RP=Q\\mathbin\{\\dot\{\\cup\}\}Rbe a fixed palette, and letVc⊆V​\(G\)V\_\{c\}\\subseteq V\(G\)be the allowed domain of each colorc∈Pc\\in P\. Define

DQ=⋃c∈QVc,DR=⋃c∈RVc\.D\_\{Q\}=\\bigcup\_\{c\\in Q\}V\_\{c\},\\qquad D\_\{R\}=\\bigcup\_\{c\\in R\}V\_\{c\}\.WhetherGGadmits a proper coloring in which every colorccis used only onVcV\_\{c\}can be decided in

O∗​\(2\|DQ\|\+2\|DR\|\)O^\{\*\}\\bigl\(2^\{\|D\_\{Q\}\|\}\+2^\{\|D\_\{R\}\|\}\\bigr\)time and exponential space\.

Theorem[3\.7](https://arxiv.org/html/2607.25973#S3.Thmtheorem7)is the combination of Lemmas 3\.11, 3\.14, and 3\.16 and Observation 3\.23 of\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]\. In\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\], partition containers were constructed precisely to prove that the domains of the color classes must admit such a two\-block grouping with non\-trivial size bounds, leading to sub\-2n2^\{n\}coloring algorithms for regular and almost\-regular graphs; see Theorems 3\.24 and 3\.25 therein\.

For later use, we rephrase the above statement in the language of forbidden vertex sets\.

###### Corollary 3\.8\(Two\-block list\-coloring\)\.

LetP=Q∪˙RP=Q\\mathbin\{\\dot\{\\cup\}\}R, and consider a list\-coloring instance over a palettePPon annn\-vertex graph\. Suppose thatA,B⊆V​\(G\)A,B\\subseteq V\(G\)satisfy

L​\(v\)⊆Qfor every​v∈A,L​\(v\)⊆Rfor every​v∈B\.L\(v\)\\subseteq Q\\quad\\text\{for every \}v\\in A,\\qquad L\(v\)\\subseteq R\\quad\\text\{for every \}v\\in B\.Then list colorability can be decided in

O∗​\(2n−\|A\|\+2n−\|B\|\)O^\{\*\}\\bigl\(2^\{n\-\|A\|\}\+2^\{n\-\|B\|\}\\bigr\)time and exponential space\. In particular, if\|A\|,\|B\|≥η​n\|A\|,\|B\|\\geq\\eta n, the running time isO∗​\(2\(1−η\)​n\)O^\{\*\}\(2^\{\(1\-\\eta\)n\}\)\.

###### Proof\.

SetVc=\{v:c∈L​\(v\)\}V\_\{c\}=\\\{v:c\\in L\(v\)\\\}\. No color inRRis allowed onAA, and no color inQQis allowed onBB\. Consequently,

DR⊆V​\(G\)∖A,DQ⊆V​\(G\)∖B\.D\_\{R\}\\subseteq V\(G\)\\setminus A,\\qquad D\_\{Q\}\\subseteq V\(G\)\\setminus B\.The result follows immediately from Theorem[3\.7](https://arxiv.org/html/2607.25973#S3.Thmtheorem7)\. ∎

## 4Warm\-up: Extending the reduction from two to three steps

As a first step, we rephrase the 2\-step reductions of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]\(from\(k\+2\)\(k\+2\)or\(k\+1\)\(k\+1\)\-coloring tokk\-list\-coloring\) in a cleaner way that would later be useful for us in the generalization\. We then extend it one step further and get a reduction from\(k\+3\)\(k\+3\)\-coloring tokk\-list\-coloring; this already gives the first sub\-2n2^\{n\}algorithm for77\-coloring\.

Zamir’s reductions follow from the\(α,Δ\)\(\\alpha,\\Delta\)\-bounded coloring result cited as Theorem[3\.5](https://arxiv.org/html/2607.25973#S3.Thmtheorem5): Given an instance of\(k\+1\)\(k\+1\)\-coloring, we consider two options\. If the graph is already\(α,Δ\)\(\\alpha,\\Delta\)\-bounded for any chosen constants, then we have a sub\-2n2^\{n\}algorithm\. Otherwise, nearly all vertices \(a\(1−α\)\(1\-\\alpha\)fraction, and we can take a very small constantα\>0\\alpha\>0\) have degrees that are large \(larger than a constantΔ\\Deltaof our choice\)\. In that second case, we can sample a very small subset of vertices and enumerate over their correct colors\. As nearly all vertices have many neighbors, this small subset is likely to hit a neighbor of the vast majority of them\. In particular, most vertices lose one color option \(as we already colored one of their neighbors\) which puts us, modulo technical details, in a\(k−1\)\(k\-1\)\-list\-coloring instance\.

Extending this idea to\(k\+2\)\(k\+2\)\-coloring already faces an obstruction: Even if we sample a large enough subset to hit the neighborhood of each high\-degree vertex more than once, it could be that in the correct coloring all of these neighbors would be assigned the same color\. Thus, the resulting color lists may remain of size\(k−1\)\(k\-1\)and not get smaller as we sample more neighbors\. When that happens for a vertex, though, it means that in the correct coloring most of its neighbors are supposed to be colored by the same color\. This is useful on its own: we are able to sample many neighbors of a high\-degree vertex and “guess” that they are all supposed to have the same color and thus can be contracted into a single vertex\. As this reduces the number of vertices in the graph, a careful analysis results in the desired reduction\.

Attempting to push this one step further to\(k\+3\)\(k\+3\)\-coloring results in a scarier\-looking obstruction, which was not yet resolved in\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]: If high\-degree vertices have their neighbors partitioned, roughly equally, between*two*color classes \(rather than one\), then a small sampled subset of vertices will only reduce the size of lists by22; at the same time, unlike the one dominant color case, knowing \(or guessing\) that many vertices are of one of two possible colors seems insufficient to assist a sub\-2n2^\{n\}algorithm\. This is because finding the correct color among these two possible colors is still costing a factor of22for each such vertex\.

Sweeping all technical details under the rug, the above sketch leaves us with a clean problem: Given a list\-coloring instance in which a reasonable fraction of the vertices have only two colors in their list, can we determine colorability in sub\-2n2^\{n\}time? This sounds rather promising, as if all lists were of size two, then this would simply be an instance of22\-SAT which can be solved in polynomial\-time\. It is thus reasonable to hope an interpolation between the size\-two and general\-size list algorithms can result in a faster algorithm in these settings\.

Indeed, in Section[4\.3](https://arxiv.org/html/2607.25973#S4.SS3)we prove that given a list\-coloring instance over a palettePPof fixed sizeKK, such that at leastbbout of thennvertices in the graph have lists of size at most two, we can determine colorability in

O∗​\(2n−b⋅qb\)O^\{\*\}\\left\(2^\{n\-b\}\\cdot q^\{b\}\\right\)time, forq=21−1/\(K2\)<2q=2^\{1\-1/\{K\\choose 2\}\}<2\.

At first glance, one could hope achieving the same result withq=1q=1is possible, as that would match the natural interpolation with the polynomial\-time algorithm for22\-SAT whenb=nb=n\. In Section[4\.4](https://arxiv.org/html/2607.25973#S4.SS4)we prove that this is impossible: assuming the Exponential Time Hypothesis \(ETH\), any such algorithm must haveq\>1q\>1\. On the other hand, while theqqwe achieve depends on the palette sizeKK, we do not rule out an algorithm in which1<q<21<q<2is independent ofKK\. This gap, which we leave open, appears to be the main reason our final list\-coloring result requires a fixed palette sizeKKrather than just fixed\-size lists\.

### 4\.1The seed\-shortening lemma

We begin by rehashing \(and slightly generalizing\) a central lemma in the reduction of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\], which will be useful for both the warm\-up and the general algorithm\.

Fix a palettePPof sizeKK\. Suppose\(k−1\)\(k\-1\)\-list\-coloring \(overPP\) has an algorithm of basea<2a<2, and consider akk\-*list*\-coloring instance\. We say a vertex is*active*if its list has size exactlykk\. Relative to a fixed witness coloringcc, call an active vertex*good*if some color in its list occurs on more thanΔ1\\Delta\_\{1\}of its neighbors in the coloringcc, and*bad*otherwise\. Note that we cannot algorithmically classify vertices to good and bad as we do not know the coloringcc\.

###### Lemma 4\.1\(Seed shortening\)\.

There are constantsβ0\>0\\beta\_\{0\}\>0,Δ1\\Delta\_\{1\}, andCS<2C\_\{S\}<2depending only onP,k,aP,k,asuch that the following holds\. There is an algorithm with running timeO∗​\(CSn\)O^\{\*\}\(C\_\{S\}^\{n\}\)with the following property: relative to every fixed witness coloringcc, if at mostβ0​n\\beta\_\{0\}nactive vertices are bad, it returns a coloring with probability at least1−exp⁡\(−Θ​\(n\)\)1\-\\exp\(\-\\Theta\(n\)\)\.

###### Proof\.

Choose every vertex independently with probability

θ=ln⁡Δ1Δ1\\theta=\\frac\{\\ln\\Delta\_\{1\}\}\{\\Delta\_\{1\}\}to form a vertex subsetZ⊆V​\(G\)Z\\subseteq V\(G\)which we call a*seed*\. Abort if\|Z\|\>4​θ​n\|Z\|\>4\\theta n; otherwise enumerate all proper list\-respecting colorings ofG​\[Z\]G\[Z\]\. For a seed coloringφ\\varphi, letWφW\_\{\\varphi\}be the active vertices outsideZZthat are not adjacent to a seed vertex colored by a color belonging to their own lists\. Abort \(the enumeration on the specificφ\\varphi\) if

\|Wφ\|\>\(β0\+4/Δ1\)​n\.\|W\_\{\\varphi\}\|\>\(\\beta\_\{0\}\+4/\\Delta\_\{1\}\)n\.Otherwise enumerate all proper list\-respecting colorings ofWφW\_\{\\varphi\}that are compatible withφ\\varphi\. Delete the explicitly colored vertices and their used colors from neighboring lists, aborting if some residual list becomes empty\. Every remaining active vertex now loses a color, so the residual instance has maximum list sizek−1k\-1and can be passed to the assumed algorithm for\(k−1\)\(k\-1\)\-list\-coloring\.

On the branch agreeing withcc, a good active vertex is missed with probability at most

\(1−θ\)Δ1≤Δ1−1\.\(1\-\\theta\)^\{\\Delta\_\{1\}\}\\leq\\Delta\_\{1\}^\{\-1\}\.The expected number of missed good active vertices is at mostn/Δ1n/\\Delta\_\{1\}, while𝔼​\[\|Z\|\]=θ​n\\mathbb\{E\}\\left\[\|Z\|\\right\]=\\theta n\. Markov’s inequality bounds the probability of each of the events

\|Z\|\>4​θ​n,\#​\{missed good active vertices\}\>4​n/Δ1\|Z\|\>4\\theta n,\\qquad\\\#\\\{\\text\{missed good active vertices\}\\\}\>4n/\\Delta\_\{1\}by1/41/4\. Hence, with probability at least1/21/2, neither event occurs\. If there are at mostβ0​n\\beta\_\{0\}nbad active vertices, then on that event the witness branch satisfies

\|Wc\|Z\|≤\(β0\+4/Δ1\)​n,\|W\_\{c\|\_\{Z\}\}\|\\leq\(\\beta\_\{0\}\+4/\\Delta\_\{1\}\)n,so it is not aborted\. The enumerated coloring ofZ∪Wc\|ZZ\\cup W\_\{c\|\_\{Z\}\}is exactly the restriction ofcc, and consequently the residual\(k−1\)\(k\-1\)\-list\-coloring instance is colorable\.

Put

σ=4​ln⁡Δ1Δ1\+β0\+4Δ1\.\\sigma=4\\frac\{\\ln\\Delta\_\{1\}\}\{\\Delta\_\{1\}\}\+\\beta\_\{0\}\+\\frac\{4\}\{\\Delta\_\{1\}\}\.For a fixed non\-aborted seedZZand a seed coloringφ\\varphi, the calls generated by all colorings ofWφW\_\{\\varphi\}cost at most

K\|Wφ\|​an−\|Z\|−\|Wφ\|\.K^\{\|W\_\{\\varphi\}\|\}a^\{n\-\|Z\|\-\|W\_\{\\varphi\}\|\}\.There are at mostK\|Z\|K^\{\|Z\|\}seed colorings\. SinceK/a≥1K/a\\geq 1, summing over all retained branches gives

∑φK\|Wφ\|​an−\|Z\|−\|Wφ\|\\displaystyle\\sum\_\{\\varphi\}K^\{\|W\_\{\\varphi\}\|\}a^\{n\-\|Z\|\-\|W\_\{\\varphi\}\|\}≤K\|Z\|​an−\|Z\|​\(K/a\)maxφ⁡\|Wφ\|\\displaystyle\\leq K^\{\|Z\|\}a^\{n\-\|Z\|\}\(K/a\)^\{\\max\_\{\\varphi\}\|W\_\{\\varphi\}\|\}≤an​\(K/a\)σ​n\.\\displaystyle\\leq a^\{n\}\(K/a\)^\{\\sigma n\}\.Generating and checking the partial colorings is bounded by the same expression up to polynomial factors\. Thus the work over all branches isO∗​\(an​\(K/a\)σ​n\)O^\{\*\}\(a^\{n\}\(K/a\)^\{\\sigma n\}\)\. We may thus chooseΔ1\\Delta\_\{1\}large enough and thenβ0\\beta\_\{0\}small enough so thatCS:=a​\(K/a\)σ<2C\_\{S\}:=a\(K/a\)^\{\\sigma\}<2\(this is true as we can makeσ\\sigmaas small a constant as we want, and asa<2a<2\)\.

The constant success probability can be amplified via repetition\. ∎

Once the parametersΔ,α\\Delta,\\alphaare fixed, define the*easy solver*EEas follows\. If at leastα​n\\alpha nvertices have degree at mostΔ\\Delta, use Theorem[3\.5](https://arxiv.org/html/2607.25973#S3.Thmtheorem5); otherwise use the seed solver\. It has baseC<2C<2and, for a suitable success probability \(which can be amplified as needed by repetition\), succeeds relative to a witness coloring whenever either the low\-degree condition holds or at mostβ0​n\\beta\_\{0\}nactive vertices are bad\.

### 4\.2Reducing to an instance with many size\-two lists

We now extend the reductions of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]by one more step, constructing a reduction from\(k\+3\)\(k\+3\)\-coloring tokk\-list\-coloring, via the aforementioned size\-two lists speedup which we then analyze in the next Section\. This Section also rephrases the reductions of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]in a significantly more useful manner for our later generalization; instead of analyzing all three steps of the reduction simultaneously, we assume as a black\-box the existing two\-step reduction and analyze only the one additional step\. That is, fix a paletteP=\[K\]P=\[K\], the previous result shows that a sub\-2n2^\{n\}algorithm for\(K−2\)\(K\-2\)\-list\-coloring over\[K\]\[K\]implies a sub\-2n2^\{n\}algorithm forKK\-coloring \(equivalently,KK\-list\-coloring over\[K\]\[K\]\)\. Thus, it suffices to prove that a sub\-2n2^\{n\}algorithm for\(K−3\)\(K\-3\)\-list\-coloring over\[K\]\[K\]implies a sub\-2n2^\{n\}algorithm for\(K−2\)\(K\-2\)\-list\-coloring over\[K\]\[K\]\.

Start with an instance of\(K−2\)\(K\-2\)\-list\-coloring over\[K\]\[K\]\. For an active vertexvv, that is a vertex with\|L​\(v\)\|=\(K−2\)\|L\(v\)\|=\(K\-2\), the complement of the list is a computable set of two colors

Qv:=P∖L​\(v\)\.Q\_\{v\}:=P\\setminus L\(v\)\.Ifvvis bad relative to a witness coloring, then only boundedly many neighbors ofvvreceive colors fromL​\(v\)L\(v\)\. Consequently, whenvvalso has sufficiently large degree, a constant sample from its neighborhood is likely to consist entirely of vertices whose witness colors lie in the pairQvQ\_\{v\}\. Restricting the sampled vertices toQvQ\_\{v\}then preserves the witness with good probability and shrinks several lists to size at most two\.

The point of taking a sample of sizerr, rather than a single neighbor, is quantitative: if we guessed that the vertexvvis bad successfully then we createrrshort lists\. By choosingrrlarge enough, the saving supplied by the binary\-list interpolation theorem outweighs the cost of succeeding in this guess\.

###### Lemma 4\.2\(Pair\-complement bootstrap\)\.

Fix a palettePPof sizeK≥4K\\geq 4\. If\(K−3\)\(K\-3\)\-list\-coloring overPPhas an algorithm running inO∗​\(an\)O^\{\*\}\(a^\{n\}\)time for somea<2a<2, then\(K−2\)\(K\-2\)\-list\-coloring overPPhas an algorithm running inO∗​\(\(2−ε\)n\)O^\{\*\}\(\(2\-\\varepsilon\)^\{n\}\)time for someε\>0\\varepsilon\>0that depends only onK,aK,a\.

###### Proof\.

Apply Lemma[4\.1](https://arxiv.org/html/2607.25973#S4.Thmtheorem1)withk=K−2k=K\-2, and run the full normalization \(of Lemma[3\.2](https://arxiv.org/html/2607.25973#S3.Thmtheorem2)\) before the algorithm starts and after every step\. Letβ0,Δ1,CS\\beta\_\{0\},\\Delta\_\{1\},C\_\{S\}be the constants supplied by that lemma\. Set

α=β02,M=\(K2\),p0=β08\.\\alpha=\\frac\{\\beta\_\{0\}\}\{2\},\\qquad M=\\binom\{K\}\{2\},\\qquad p\_\{0\}=\\frac\{\\beta\_\{0\}\}\{8\}\.Choose an integerr≥2r\\geq 2sufficiently large that

λ:=M​log2⁡\(1/p0\)r<1\.\\lambda:=\\frac\{M\\log\_\{2\}\(1/p\_\{0\}\)\}\{r\}<1\.Finally, put

B=\(K−2\)​Δ1,Δ=r​\(1\+B\)\.B=\(K\-2\)\\Delta\_\{1\},\\qquad\\Delta=r\(1\+B\)\.
For a current instance onssvertices \(the number of vertices may decrease from the originalnndue to the normalization steps\), define the*easy solver*EEas follows\. If at leastα​s\\alpha svertices have degree at mostΔ\\Delta, apply Theorem[3\.5](https://arxiv.org/html/2607.25973#S3.Thmtheorem5); otherwise apply the seed solver from Lemma[4\.1](https://arxiv.org/html/2607.25973#S4.Thmtheorem1)\. Both alternatives are exponential algorithms with a base smaller than22\. Thus there is a constantC<2C<2such thatEEruns inO∗​\(Cs\)O^\{\*\}\(C^\{s\}\)time and succeeds with probability at least12\\frac\{1\}\{2\}, relative to any fixed witness, whenever either

1. \(i\)at leastα​s\\alpha svertices have degree at mostΔ\\Delta; or
2. \(ii\)at mostβ0​s\\beta\_\{0\}sactive vertices are bad\.

For an instanceII, letn​\(I\)n\(I\)be its number of vertices and letb​\(I\)b\(I\)be the number of vertices whose lists have size at most two\. Define

w​\(I\):=n​\(I\)−b​\(I\)M\.w\(I\):=n\(I\)\-\\frac\{b\(I\)\}\{M\}\.In the following Section[4\.3](https://arxiv.org/html/2607.25973#S4.SS3), we show thatIIcan be solved deterministically inO∗​\(2w​\(I\)\)O^\{\*\}\(2^\{w\(I\)\}\)time\. We next describe a*lucky move*that decreasesww\.

LetIIbe a fully normalized current instance\. Choose a uniformly random vertexvv, and abort the move unlessvvis active anddeg⁡\(v\)\>Δ\\deg\(v\)\>\\Delta\. For such a vertex, let

Qv=P∖L​\(v\);Q\_\{v\}=P\\setminus L\(v\);because\|L​\(v\)\|=K−2\|L\(v\)\|=K\-2, the setQvQ\_\{v\}has size two\. Choose a uniformly randomrr\-element subsetT⊆N​\(v\)T\\subseteq N\(v\), and simultaneously replace

L​\(u\)byL​\(u\)∩Qv\(u∈T\)\.L\(u\)\\quad\\text\{by\}\\quad L\(u\)\\cap Q\_\{v\}\\qquad\(u\\in T\)\.Reject the move if an empty list is produced; otherwise apply full normalization\. We call a move that is neither aborted nor rejected*completed*\.

Fix a witness coloringccof the current instance\. Suppose that neither of the two easy conditions \(i\) or \(ii\) above holds\. There are then more thanβ0​s\\beta\_\{0\}sbad active vertices, while fewer thanα​s\\alpha svertices have degree at mostΔ\\Delta\. Hence more than

\(β0−α\)​s=β0​s2\(\\beta\_\{0\}\-\\alpha\)s=\\frac\{\\beta\_\{0\}s\}\{2\}vertices are simultaneously bad, active, and of degree greater thanΔ\\Delta\. The probability that the random vertexvvis one of these vertices is therefore greater thanβ0/2\\beta\_\{0\}/2\.

vvL​\(v\)=P∖QvL\(v\)=P\\setminus Q\_\{v\}deg⁡\(v\)\>Δ\\deg\(v\)\>\\Delta⋮\\vdotsa1a\_\{1\}a2a\_\{2\}aK−2a\_\{K\-2\}≤Δ1\\leq\\Delta\_\{1\}of eachai∈L​\(v\)a\_\{i\}\\in L\(v\)at mostB=\(K−2\)​Δ1B=\(K\-2\)\\Delta\_\{1\}in totalWitness colors inQv=\{q1,q2\}Q\_\{v\}=\\\{q\_\{1\},q\_\{2\}\\\}\>Δ−B\>\\Delta\-BneighborsFigure 1:An eligible vertexvvunder the witnesscc\.Condition on choosing such a vertex \(which we call*eligible*\)\. Sincevvis bad, each color inL​\(v\)L\(v\)appears on at mostΔ1\\Delta\_\{1\}of its neighbors undercc\. Thus at most

\(K−2\)​Δ1=B\(K\-2\)\\Delta\_\{1\}=Bneighbors ofvvreceive a witness color inL​\(v\)L\(v\); every other neighbor receives a witness color inQvQ\_\{v\}\. Expose the members of the sampled setTTone at a time\. At any point during therrdraws, there are at least

neighbors remaining\. At mostBBof the remaining neighbors have witness colors outsideQvQ\_\{v\}\. See Figure[1](https://arxiv.org/html/2607.25973#S4.F1)for illustration\. Each draw therefore has conditional success probability at least1−1/r1\-1/r, and

Pr⁡\[c​\(T\)⊆Qv\|v​is eligible\]≥\(1−1/r\)r≥14\.\\Pr\\\!\\left\[c\(T\)\\subseteq Q\_\{v\}\\,\\middle\|\\,v\\text\{ is eligible\}\\right\]\\geq\(1\-1/r\)^\{r\}\\geq\\frac\{1\}\{4\}\.Together with the probability of choosing an eligible vertex, this shows that whenever the state is not in one of the easy options \(i\) or \(ii\), a lucky move preserves the fixed witness with probability at least

β02⋅14=p0\.\\frac\{\\beta\_\{0\}\}\{2\}\\cdot\\frac\{1\}\{4\}=p\_\{0\}\.On this event every intersection in \(4\.5\) contains the witness color, so the move is not rejected and the subsequent normalization also preserves the witness\. After completing a lucky move we have

w​\(I′\)≤w​\(I\)−rM,w\(I^\{\\prime\}\)\\leq w\(I\)\-\\frac\{r\}\{M\},whereI′I^\{\\prime\}is the normalized instance after the move\. Indeed, because rule \(N\) was exhausted before the move, the edgeu​vuvimpliesL​\(u\)∩L​\(v\)≠∅L\(u\)\\cap L\(v\)\\neq\\varnothingfor everyu∈Tu\\in T\. SinceQvQ\_\{v\}is disjoint fromL​\(v\)L\(v\), intersectingL​\(u\)L\(u\)withQvQ\_\{v\}strictly shortensL​\(u\)L\(u\)\. On a completed move the resulting list is nonempty and has size at most two\. Perform allrrintersections before propagating singletons \(as part of the full normalization\)\. If\|L​\(u\)\|≥3\|L\(u\)\|\\geq 3before the move, thenuubecomes a short\-list vertex, which decreaseswwby1/M1/M\. If\|L​\(u\)\|=2\|L\(u\)\|=2, then strict shortening makesuua singleton\. Its subsequent deletion decreasesn​\(I\)n\(I\)andb​\(I\)b\(I\)by one, and therefore decreaseswwby

1−1M≥1M\.1\-\\frac\{1\}\{M\}\\geq\\frac\{1\}\{M\}\.The vertices inTTare distinct, so theserrcontributions add\. All further singleton propagation can only decreaseww: deleting a short\-list vertex decreases it by1−1/M1\-1/M, while shortening a longer list to size at most two decreases it by1/M1/M\. This proves \(4\.8\)\.

Letnnbe the number of vertices of the original input and define

d=min⁡\{12,1−log⁡C2​λ\}\>0,m=⌊d​M​nr⌋\.d=\\min\\left\\\{\\frac\{1\}\{2\},\\frac\{1\-\\log C\}\{2\\lambda\}\\right\\\}\>0,\\qquad m=\\left\\lfloor\\frac\{dMn\}\{r\}\\right\\rfloor\.Ifm=0m=0, thennnis bounded by a constant depending only on the fixed parameters, and the instance may be solved by exhaustive search\. Assume henceforth thatm≥1m\\geq 1\.

Consider the following*trial*starting from the original instance and performing at mostmmlucky moves: At each of themmlucky move attempts, first run the easy algorithmEE\. IfEEreturns a coloring, return it\. Otherwise perform one lucky move; an abort or rejection ends the current trial\. Aftermmcompleted lucky moves, invoke the binary interpolation \(Theorem[4\.4](https://arxiv.org/html/2607.25973#S4.Thmtheorem4), proven in Section[4\.3](https://arxiv.org/html/2607.25973#S4.SS3)\) on the remaining instance\.

To prove correctness, fix a witness coloringccof the original instance\. Call a current state*witness\-compatible*if every remaining list contains the color assigned by the restriction ofcc\. We claim, by \(backward\) induction onhh, that from any witness\-compatible state withhhlucky moves remaining, the rest of the trial succeeds with probability at least

12​p0h\.\\frac\{1\}\{2\}p\_\{0\}^\{h\}\.Forh=0h=0, the deterministic interpolation algorithm succeeds with probability one, which is at least12\\frac\{1\}\{2\}\. Supposeh≥1h\\geq 1\. If the current state is easy,EEsucceeds with probability at least12\\frac\{1\}\{2\}, which is at least12​p0h\\frac\{1\}\{2\}p\_\{0\}^\{h\}\. Otherwise, the lucky move preserves the witness with probability at leastp0p\_\{0\}, after which the induction hypothesis applies\.

In particular, one trial succeeds with probability at least12​p0m\\frac\{1\}\{2\}p\_\{0\}^\{m\}\. Run

R=⌈2​np0m⌉R=\\left\\lceil\\frac\{2n\}\{p\_\{0\}^\{m\}\}\\right\\rceilindependent trials\. On a yes\-instance the probability they all fail is

\(1−12​p0m\)R≤exp⁡\(−12​p0m​R\)≤e−n\.\\left\(1\-\\frac\{1\}\{2\}p\_\{0\}^\{m\}\\right\)^\{R\}\\leq\\exp\\left\(\-\\frac\{1\}\{2\}p\_\{0\}^\{m\}R\\right\)\\leq e^\{\-n\}\.
It remains to verify that the amplified running time is still sub\-2n2^\{n\}\. By \(4\.8\), a trial reaching its terminal call satisfies

w​\(Im\)≤n−m​rM≤\(1−d\)​n\+O​\(1\)\.w\(I\_\{m\}\)\\leq n\-\\frac\{mr\}\{M\}\\leq\(1\-d\)n\+O\(1\)\.Thus the terminal call costsO∗​\(2\(1−d\)​n\)O^\{\*\}\(2^\{\(1\-d\)n\}\), whereas all easy calls within one trial together costO∗​\(Cn\)=O∗​\(2log⁡C⋅n\)O^\{\*\}\(C^\{n\}\)=O^\{\*\}\(2^\{\\log C\\cdot n\}\)\. The lucky moves take only polynomial time\. Moreover,

p0−m≤2\(d​M​n/r\)​log2⁡\(1/p0\)=2λ​d​n\.p\_\{0\}^\{\-m\}\\leq 2^\{\(dMn/r\)\\log\_\{2\}\(1/p\_\{0\}\)\}=2^\{\\lambda dn\}\.After multiplication by the number of trials, the exponential parts of the easy\-call and terminal costs are therefore bounded by

2\(log⁡C\+λ​d\)​nand2\(1−d\+λ​d\)​n,2^\{\(\\log C\+\\lambda d\)n\}\\quad\\text\{and\}\\quad 2^\{\(1\-d\+\\lambda d\)n\},respectively\. By the choice ofddand byλ<1\\lambda<1,

log⁡C\+λ​d≤1\+log⁡C2<1,1−d\+λ​d=1−\(1−λ\)​d<1\.\\log C\+\\lambda d\\leq\\frac\{1\+\\log C\}\{2\}<1,\\qquad 1\-d\+\\lambda d=1\-\(1\-\\lambda\)d<1\.Hence, for

γ=max⁡\{log⁡C\+λ​d,1−\(1−λ\)​d\}<1,\\gamma=\\max\\\{\\log C\+\\lambda d,\\;1\-\(1\-\\lambda\)d\\\}<1,the total running time isO∗​\(2γ​n\)O^\{\*\}\(2^\{\\gamma n\}\)\. Equivalently it isO∗​\(\(2−ε\)n\)O^\{\*\}\(\(2\-\\varepsilon\)^\{n\}\), whereε=2−2γ\>0\\varepsilon=2\-2^\{\\gamma\}\>0\.

Every successful subroutine returns a coloring of a restriction of the original instance; forced assignments are then restored in reverse order\. Since the algorithm only shrinks lists, deletes only edges whose endpoint lists are disjoint, and verifies every returned coloring, it never accepts a no\-instance\. Its only possible error is the false\-negative event bounded in \(4\.12\)\. This proves the lemma\. ∎

Thus, together with the previous reductions from\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]we get the following\.

###### Corollary 4\.3\(Three\-color gap\)\.

For every fixed integerk≥4k\\geq 4, a sub\-2n2^\{n\}algorithm for\(k−3\)\(k\-3\)\-list\-coloring implies a sub\-2n2^\{n\}algorithm forkk\-coloring\. In particular, the known44\-list\-coloring algorithm of\[[BE05](https://arxiv.org/html/2607.25973#bib.bib2)\]yields such an algorithm for77\-coloring\.

For completeness, we include a pseudo\-code of the entire reduction described in Lemma[4\.2](https://arxiv.org/html/2607.25973#S4.Thmtheorem2)in Algorithm[1](https://arxiv.org/html/2607.25973#algorithm1)\.

Input:A list\-coloring instance

I=\(G,L\)I=\(G,L\)over

\[K\]\[K\]with

\|L​\(v\)\|≤K−2\|L\(v\)\|\\leq K\-2for every

vv
Output:

𝖸𝖤𝖲\\mathsf\{YES\}or

𝖭𝖮\\mathsf\{NO\}
Let

m,R,r,Δm,R,r,\\Deltabe the constants and parameters fixed in the proof;

I0←FullNormalization​\(I\)I\_\{0\}\\leftarrow\\textsc\{FullNormalization\}\(I\);

if*I0I\_\{0\}is infeasible*then

return

𝖭𝖮\\mathsf\{NO\};

if*m=0m=0*then

return

BinaryInterpolation​\(I0\)\\textsc\{BinaryInterpolation\}\(I\_\{0\}\);

for*t←1t\\leftarrow 1toRR*do

I←I0I\\leftarrow I\_\{0\};

for*j←1j\\leftarrow 1tomm*do

if**EasySolver\-*​E​\(I\)\\textsc\{EasySolver\-\}E\(I\)finds a coloring*then

return

𝖸𝖤𝖲\\mathsf\{YES\};

Choose

vvuniformly at random from

V​\(I\)V\(I\);

if*\|LI​\(v\)\|≠K−2\|L\_\{I\}\(v\)\|\\neq K\-2ordegI⁡\(v\)≤Δ\\deg\_\{I\}\(v\)\\leq\\Delta*then

continue with the next trial;

Qv←\[K\]∖LI​\(v\)Q\_\{v\}\\leftarrow\[K\]\\setminus L\_\{I\}\(v\);

Choose a uniformly random

rr\-element set

T⊆NI​\(v\)T\\subseteq N\_\{I\}\(v\);

Simultaneously replace

LI​\(u\)L\_\{I\}\(u\)by

LI​\(u\)∩QvL\_\{I\}\(u\)\\cap Q\_\{v\}for every

u∈Tu\\in T;

if*one of the resulting lists is empty*then

continue with the next trial;

I←FullNormalization​\(I\)I\\leftarrow\\textsc\{FullNormalization\}\(I\);

if*IIis infeasible*then

continue with the next trial;

if**BinaryInterpolation*​\(I\)\\textsc\{BinaryInterpolation\}\(I\)returns𝖸𝖤𝖲\\mathsf\{YES\}*then

return

𝖸𝖤𝖲\\mathsf\{YES\};

return

𝖭𝖮\\mathsf\{NO\};

Algorithm 1The pair\-complement bootstrapThe instruction to continue with the next trial abandons the current inner loop and returns to the outer repetition loop\.

### 4\.3Interpolation algorithm for instances with many size\-two lists

The remaining component is the black\-box theorem we used in the proof of Lemma[4\.2](https://arxiv.org/html/2607.25973#S4.Thmtheorem2): a faster algorithm for solving list\-coloring instances over a palette of sizeKKwhere many of the lists are of size \(at most\) two\. The next theorem is stated independently of the reduction and may be useful elsewhere\.

###### Theorem 4\.4\(Binary\-list interpolation\)\.

Fix a palettePPof sizeK≥2K\\geq 2\. If a list\-coloring instance overPPonnnvertices hasbbvertices with lists of size at most two, it can be solved deterministically in

O∗​\(2n−b/\(K2\)\)O^\{\*\}\\\!\\left\(2^\{n\-b/\\binom\{K\}\{2\}\}\\right\)time\. A coloring can be recovered within the same bound\.

The algorithm we present is rooted at the following simple observation: Since there are onlyKKcolors in the palette, many of thebbshort\-list vertices have exactly the same list of two colors\. Let’s call these special colorsc1c\_\{1\}andc2c\_\{2\}\. If we are given a partial coloring ofGGin which only vertices with non\-special colors inP∖\{c1,c2\}P\\setminus\\\{c\_\{1\},c\_\{2\}\\\}are colored – then we can test if this partial coloring can be extended to a full coloring in polynomial time; that is because the remaining instance is simply an instance of22\-list\-coloring \(or in fact,22\-coloring as it is entirely over the palette\{c1,c2\}\\\{c\_\{1\},c\_\{2\}\\\}\)\. Furthermore, the test above*does not depend*on the partial coloring at all \- just on which vertices are colored by any color out of\{c1,c2\}\\\{c\_\{1\},c\_\{2\}\\\}, and which are not\. Hence, we can remove the vertices with the special short\-list from the graph, and then use the algorithm cited in Lemma[3\.3](https://arxiv.org/html/2607.25973#S3.Thmtheorem3)to find all induced subgraphs that are colorable with only colors fromP∖\{c1,c2\}P\\setminus\\\{c\_\{1\},c\_\{2\}\\\}; then attempt extending each such option to a full coloring in polynomial time\.

###### Proof of Theorem[4\.4](https://arxiv.org/html/2607.25973#S4.Thmtheorem4)\.

First exhaust singleton propagation as part of a full normalization step\. If a singleton is deleted, or if deleting its color shortens another list, the potentialn−b/\(K2\)n\-b/\\binom\{K\}\{2\}cannot increase, where herebbcounts all lists of size at most two\. More explicitly, deleting a short\-list vertex decreases the potential by1−1/\(K2\)1\-1/\\binom\{K\}\{2\}, and shortening a longer list to size at most two decreases it by1/\(K2\)1/\\binom\{K\}\{2\}\. After propagation every remaining short list has size exactly two\. It therefore suffices to prove the claim in that normalized case; relabel its parameters asn,bn,b\.

LetM=\(K2\)M=\\binom\{K\}\{2\}\. Among the possible binary lists, choose a pairQ⊆PQ\\subseteq Poccurring on a largest set

S=\{v:L​\(v\)=Q\}\.S=\\\{v:L\(v\)=Q\\\}\.Thens:=\|S\|≥b/Ms:=\|S\|\\geq b/M\. PutH=V​\(G\)∖SH=V\(G\)\\setminus S\.

Keep the original listsLLunchanged and define a separate outside\-list instance onHHby

Lout​\(v\)=L​\(v\)∖Q\.L\_\{\\mathrm\{out\}\}\(v\)=L\(v\)\\setminus Q\.An empty auxiliary list is allowed: it simply makes every subgraph containing that vertex infeasible in the outside\-list coloring instance\. By Lemma[3\.3](https://arxiv.org/html/2607.25973#S3.Thmtheorem3), inO∗​\(2\|H\|\)O^\{\*\}\(2^\{\|H\|\}\)total time we know, for everyX⊆HX\\subseteq H, whetherG​\[X\]G\[X\]is colorable fromLoutL\_\{\\mathrm\{out\}\}\.

For every such colorableXX, restrict each vertex ofV​\(G\)∖XV\(G\)\\setminus Xfrom its original list toL​\(v\)∩QL\(v\)\\cap Qand test the resulting instance by 2\-SAT\. This is solved exactly and deterministically in polynomial time\. Given a full coloring, takeXXto be the vertices ofHHcolored outsideQQ\. Conversely, an outside\-QQcoloring ofXXand aQQ\-coloring of its complement combine because endpoints of an edge crossing the cut use disjoint palettes\.

H=V​\(G\)∖SH=V\(G\)\\setminus SS=\{v:L​\(v\)=Q\}S=\\\{v:L\(v\)=Q\\\}X⊆HX\\subseteq HLout​\(v\)=L​\(v\)∖QL\_\{\\mathrm\{out\}\}\(v\)=L\(v\)\\setminus QH∖XH\\setminus XlistsL​\(v\)∩QL\(v\)\\cap QEvery list isQQFigure 2:The decomposition used by the binary\-list interpolation algorithm\.There are2\|H\|=2n−s2^\{\|H\|\}=2^\{n\-s\}subsets and polynomial work per subset\. Thus the running time is at most

O∗​\(2n−s\)≤O∗​\(2n−b/M\)\.O^\{\*\}\(2^\{n\-s\}\)\\leq O^\{\*\}\\\!\\left\(2^\{n\-b/M\}\\right\)\.After finding a successfulXX, we can also find an explicit coloring of it inO∗​\(2\|X\|\)O^\{\*\}\(2^\{\|X\|\}\)time\. This reconstructs the outside\-QQcoloring in at mostO∗​\(2\|H\|\)O^\{\*\}\(2^\{\|H\|\}\)additional time; 2\-SAT returns the complementary coloring\. Thus a full coloring is recovered within the same bound\. ∎

For completeness, we include the pseudo\-code in Algorithm[2](https://arxiv.org/html/2607.25973#algorithm2)and an illustration of the decomposition in Figure[2](https://arxiv.org/html/2607.25973#S4.F2)\.

Input:A list\-coloring instance

I=\(G,L\)I=\(G,L\)over a fixed palette

PP
Output:

𝖸𝖤𝖲\\mathsf\{YES\}if

IIis list colorable, and

𝖭𝖮\\mathsf\{NO\}otherwise

I←FullNormalization​\(I\)I\\leftarrow\\textsc\{FullNormalization\}\(I\);

if*IIis infeasible*then

return

𝖭𝖮\\mathsf\{NO\};

Choose a pair

Q∈\(P2\)Q\\in\\binom\{P\}\{2\}maximizing

\|\{v∈V​\(G\):L​\(v\)=Q\}\|\\bigl\|\\\{v\\in V\(G\):L\(v\)=Q\\\}\\bigr\|\.

Set

S←\{v∈V​\(G\):L​\(v\)=Q\},H←V​\(G\)∖S\.S\\leftarrow\\\{v\\in V\(G\):L\(v\)=Q\\\},\\;H\\leftarrow V\(G\)\\setminus S\.
For every

v∈Hv\\in H, set

Lout​\(v\)←L​\(v\)∖QL\_\{\\mathrm\{out\}\}\(v\)\\leftarrow L\(v\)\\setminus Q\.

𝒜←AllInducedListSubinstances​\(G​\[H\],Lout\)\\mathcal\{A\}\\leftarrow\\textsc\{AllInducedListSubinstances\}\(G\[H\],L\_\{\\mathrm\{out\}\}\);

for*eachX⊆HX\\subseteq Hwith𝒜​\[X\]=𝖸𝖤𝖲\\mathcal\{A\}\[X\]=\\mathsf\{YES\}*do

For every

v∈V​\(G\)∖Xv\\in V\(G\)\\setminus X, set

LQ​\(v\)←L​\(v\)∩Q\.L\_\{Q\}\(v\)\\leftarrow L\(v\)\\cap Q\.
if**2SAT*​\(G​\[V​\(G\)∖X\],LQ\)=𝖸𝖤𝖲\\textsc\{2SAT\}\(G\[V\(G\)\\setminus X\],L\_\{Q\}\)=\\mathsf\{YES\}*then

return

𝖸𝖤𝖲\\mathsf\{YES\};

return

𝖭𝖮\\mathsf\{NO\};

Algorithm 2Binary\-list interpolation
### 4\.4An ETH\-based lower bound for size\-two lists interpolation

The running time in Theorem[4\.4](https://arxiv.org/html/2607.25973#S4.Thmtheorem4)can equivalently be written as

O∗​\(2n−b​qKb\),qK=21−1/\(K2\)<2\.O^\{\*\}\\\!\\left\(2^\{n\-b\}q\_\{K\}^\{b\}\\right\),\\qquad q\_\{K\}=2^\{\\,1\-1/\\binom\{K\}\{2\}\}<2\.Thus a vertex with a general list contributes a factor of22, whereas a vertex with a list of size at most two contributes the smaller factorqKq\_\{K\}\. Since an instance in which every list has size at most two is solvable in polynomial time, it is natural to ask whether the endpointq=1q=1can be attained\. This would correspond to both desired endpoints of the interpolation: atb=0b=0, we simply solve a standard list\-coloring instance inO∗​\(2n\)O^\{\*\}\(2^\{n\}\)time, and atb=nb=nwe solve a22\-list\-coloring instance in polynomial time\.

In this section we show that this optimistic endpointq=1q=1is impossible under the Exponential Time Hypothesis\. In fact, the reduction below rules out a whole interval of constants larger than one\. The palette used by the reduction depends on one fixed CSP domain size, but not on the number of variables\. Consequently, the lower bound applies even if the hidden constants in the list\-coloring algorithm are allowed to depend arbitrarily on the fixed palette\.

###### Proposition 4\.5\(Palette\-independent interpolation requiresq\>1q\>1\)\.

Suppose that there is a constantq∈\[1,2\]q\\in\[1,2\], independent of the palette, such that the following holds for every fixed finite palettePP: an instance overPPwithuuvertices whose lists have size at least three andbbvertices whose lists have size at most two can be solved in

O∗​\(2u​qb\)O^\{\*\}\\\!\\left\(2^\{u\}q^\{b\}\\right\)time\. Assuming ETH, there is an absolute constantqETH\>1q\_\{\\mathrm\{ETH\}\}\>1such that necessarilyq≥qETHq\\geq q\_\{\\mathrm\{ETH\}\}\. In particular, no such algorithm exists withq=1q=1\.

###### Proof\.

We construct a reduction from bounded\-frequency general\(d,2\)\(d,2\)\-CSP\. As cited in Section[3](https://arxiv.org/html/2607.25973#S3), Traxler\[[TRA08](https://arxiv.org/html/2607.25973#bib.bib5)\]proved that there is an absolute constantc\>0c\>0such that, for every fixed domain sizedd, there is a constantF​\(d\)F\(d\)for which\(d,2\)\(d,2\)\-CSP onnnvariables requires timedc​nd^\{cn\}under ETH even when every variable occurs in at mostF​\(d\)F\(d\)constraints\. The important points for us are thatccis independent ofddand thatF​\(d\)F\(d\)is independent ofnn\.

Fix a domain sizedd, and consider such a bounded\-frequency CSP instance with variable set𝒳\\mathcal\{X\}\. We build a list\-coloring instance out of it\. Absorb every unary constraint into a setAx⊆\[d\]A\_\{x\}\\subseteq\[d\]of allowed values \(colors\) for its variablexx\. If someAxA\_\{x\}is empty, the instance is immediately unsatisfiable\. Every binary constraint on distinct variablesx,yx,yis equivalently the conjunction of its forbidden assignments

\(x≠a\)∨\(y≠b\),\(x\\neq a\)\\lor\(y\\neq b\),one for every pair\(a,b\)∈\[d\]2\(a,b\)\\in\[d\]^\{2\}disallowed by that constraint\.

LetJJbe the*primal graph*of the CSP: its vertices are the variables, and two variables are adjacent if they occur together in a binary constraint\. Since every variable occurs in at mostF​\(d\)F\(d\)constraints,JJhas maximum degree at mostF​\(d\)F\(d\)\. We can therefore greedily compute a proper coloring

τ:𝒳⟶\[F​\(d\)\+1\]\.\\tau:\\mathcal\{X\}\\longrightarrow\[F\(d\)\+1\]\.The valueτ​\(x\)\\tau\(x\)will serve only as a role identifying the variablexxamong the variables that may interact with it\.

Construct a list\-coloring instance over the palette

Pd=\{⊥\}∪\(\[F​\(d\)\+1\]×\[d\]\)\.P\_\{d\}=\\\{\\bot\\\}\\cup\\bigl\(\[F\(d\)\+1\]\\times\[d\]\\bigr\)\.Sinceddis fixed, this is a fixed palette\. For each CSP variablex∈𝒳x\\in\\mathcal\{X\}, introduce a*variable vertex*vxv\_\{x\}with list

L​\(vx\)=\{\(τ​\(x\),a\):a∈Ax\}\.L\(v\_\{x\}\)=\\\{\(\\tau\(x\),a\):a\\in A\_\{x\}\\\}\.For everyx∈𝒳x\\in\\mathcal\{X\}and everya∈\[d\]a\\in\[d\], introduce a*selector vertex*sx,as\_\{x,a\}, add the edge\(vx,sx,a\)\(v\_\{x\},s\_\{x,a\}\), and set

L​\(sx,a\)=\{⊥,\(τ​\(x\),a\)\}\.L\(s\_\{x,a\}\)=\\\{\\bot,\(\\tau\(x\),a\)\\\}\.Finally, for every forbidden assignment\(x=a,y=b\)\(x=a,y=b\), add the edge

\(sx,a,sy,b\)\.\(s\_\{x,a\},s\_\{y,b\}\)\.All selector vertices have lists of size exactly two\. See Figure[3](https://arxiv.org/html/2607.25973#S4.F3)for an illustration of the construction\.

vxv\_\{x\}vyv\_\{y\}⊥\\bot⊥\\botsx,as\_\{x,a\}sy,bs\_\{y,b\}L​\(vx\)=\{\(τ​\(x\),r\):r∈Ax\}L\(v\_\{x\}\)=\\\{\(\\tau\(x\),r\):r\\in A\_\{x\}\\\}L​\(vy\)=\{\(τ​\(y\),r\):r∈Ay\}L\(v\_\{y\}\)=\\\{\(\\tau\(y\),r\):r\\in A\_\{y\}\\\}Addsx,rs\_\{x,r\}for everyr∈\[d\]r\\in\[d\], withL​\(sx,r\)=\{⊥,\(τ​\(x\),r\)\}L\(s\_\{x,r\}\)=\\\{\\bot,\(\\tau\(x\),r\)\\\}Addsy,rs\_\{y,r\}for everyr∈\[d\]r\\in\[d\], withL​\(sy,r\)=\{⊥,\(τ​\(y\),r\)\}L\(s\_\{y,r\}\)=\\\{\\bot,\(\\tau\(y\),r\)\\\}\(x≠a\)∨\(y≠b\)\(x\\neq a\)\\lor\(y\\neq b\)Figure 3:Encoding one forbidden assignment of a binary CSP constraint\. Each CSP variablez∈\{x,y\}z\\in\\\{x,y\\\}is represented by a variable vertexvzv\_\{z\}and one binary\-list selectorsz,rs\_\{z,r\}for everyr∈\[d\]r\\in\[d\]\. Ifvxv\_\{x\}receives\(τ​\(x\),a\)\(\\tau\(x\),a\), its edge tosx,as\_\{x,a\}forces that selector to receive⊥\\bot, and similarlyy=by=bforcessy,bs\_\{y,b\}to receive⊥\\bot\. The emphasized selector edge therefore forbids the two assignments simultaneously\. Sinceτ​\(x\)≠τ​\(y\)\\tau\(x\)\\neq\\tau\(y\), the selectors’ non\-⊥\\botcolors do not create an unintended conflict\.We claim that the CSP instance is satisfiable if and only if the constructed list instance is colorable\. Suppose first thatf:𝒳→\[d\]f:\\mathcal\{X\}\\to\[d\]is a satisfying CSP assignment\. Color

vx​by​\(τ​\(x\),f​\(x\)\),v\_\{x\}\\ \\text\{by\}\\ \(\\tau\(x\),f\(x\)\),colorsx,f​\(x\)s\_\{x,f\(x\)\}by⊥\\bot, and color every other selectorsx,as\_\{x,a\}by\(τ​\(x\),a\)\(\\tau\(x\),a\)\. Every edge between a variable vertex and one of its selectors is proper\. Now consider an edge\(sx,a,sy,b\)\(s\_\{x,a\},s\_\{y,b\}\)corresponding to a forbidden assignment\. Its two endpoints cannot both receive⊥\\bot, since that would meanf​\(x\)=af\(x\)=aandf​\(y\)=bf\(y\)=b\. If both endpoints receive their non\-⊥\\botcolors, then those colors are also different because\(x,y\)∈E​\(J\)\(x,y\)\\in E\(J\)andτ\\tauis a proper coloring, henceτ​\(x\)≠τ​\(y\)\\tau\(x\)\\neq\\tau\(y\)\. Thus the constructed coloring is proper\.

Conversely, consider any list coloring of the constructed instance\. The color ofvxv\_\{x\}uniquely determines a valuef​\(x\)∈Axf\(x\)\\in A\_\{x\}through

c​\(vx\)=\(τ​\(x\),f​\(x\)\)\.c\(v\_\{x\}\)=\(\\tau\(x\),f\(x\)\)\.The edge\(vx,sx,f​\(x\)\)\(v\_\{x\},s\_\{x,f\(x\)\}\)then forcesc​\(sx,f​\(x\)\)=⊥c\(s\_\{x,f\(x\)\}\)=\\bot\. Ifffselected a forbidden assignment\(x=a,y=b\)\(x=a,y=b\), both endpoints of the edge\(sx,a,sy,b\)\(s\_\{x,a\},s\_\{y,b\}\)would consequently receive⊥\\bot, contradicting properness\. Thereforeffsatisfies every CSP constraint, proving the claim\.

It remains to count the two types of lists\. Let

t=\|\{x∈𝒳:\|Ax\|≤2\}\|\.t=\\bigl\|\\\{x\\in\\mathcal\{X\}:\|A\_\{x\}\|\\leq 2\\\}\\bigr\|\.There aren−tn\-tvariable vertices with lists of size at least three andttvariable vertices with lists of size at most two\. In addition, there are exactlyd​ndnselector vertices, all with binary lists\. Hence the constructed instance has

u=n−t,b=d​n\+t\.u=n\-t,\\qquad b=dn\+t\.The assumed interpolation algorithm would solve it, forq≤2q\\leq 2, in

O∗​\(2u​qb\)\\displaystyle O^\{\*\}\\\!\\left\(2^\{u\}q^\{b\}\\right\)=O∗​\(2n−t​qd​n\+t\)\\displaystyle=O^\{\*\}\\\!\\left\(2^\{n\-t\}q^\{dn\+t\}\\right\)=O∗​\(\(2​qd\)n​\(q/2\)t\)\\displaystyle=O^\{\*\}\\\!\\left\(\(2q^\{d\}\)^\{n\}\(q/2\)^\{t\}\\right\)≤O∗​\(\(2​qd\)n\)\.\\displaystyle\\leq O^\{\*\}\\\!\\left\(\(2q^\{d\}\)^\{n\}\\right\)\.
Choose a sufficiently large fixed integerd0d\_\{0\}such thatd0c\>2d\_\{0\}^\{c\}\>2and\(d0c/2\)1/d0<2\\left\(d\_\{0\}^\{c\}/2\\right\)^\{1/d\_\{0\}\}<2, and define

qETH=\(d0c2\)1/d0\>1\.q\_\{\\mathrm\{ETH\}\}=\\left\(\\frac\{d\_\{0\}^\{c\}\}\{2\}\\right\)^\{1/d\_\{0\}\}\>1\.Ifq<qETHq<q\_\{\\mathrm\{ETH\}\}, then

2​qd0<d0c,2q^\{d\_\{0\}\}<d\_\{0\}^\{c\},and the resulting algorithm would contradict Traxler’s lower bound for bounded\-frequency\(d0,2\)\(d\_\{0\},2\)\-CSP\. ∎

This proposition therefore leaves open a still interesting possibility: is there a universal constantq<2q<2, independent of the palette size, for size\-two list interpolation?

### 4\.5Reflection time

This section provides a good understanding of both the technical basis for the general algorithm as well as the apparent obstacle limiting our result from extension to list\-coloring with unbounded color palettes\.

In terms of generalization, at first glance we may be discouraged from extending the present reduction further: While a list\-coloring instance with many lists of size two seems like a naturally easier problem, due to the polynomial\-time algorithm for the extreme case of only such size two lists, the same is no longer true for larger lists\. There is no apriori reason to believe that an instance with many lists of size three or four is easier than a general instance\. A glimpse of hope though emerges from the recursive structure of our constructions\. If we already have a sub\-2n2^\{n\}algorithm forkk\-list\-coloring over\[K\]\[K\], we may hope that an instance with larger lists in which many lists are guaranteed to be of sizes at mostkkmight still have a faster solution\. Materializing this hope is not straightforward though, and a combination of tools appearing in the size\-two list interpolation algorithm with tools from the hypergraph container approach in\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]is needed to do so\. We do that in Section[5](https://arxiv.org/html/2607.25973#S5)\.

As for the obstruction, we make the following observation\. The interpolation constantqK=21−1/\(K2\)<2q\_\{K\}=2^\{\\,1\-1/\\binom\{K\}\{2\}\}<2we obtain in Section[4\.3](https://arxiv.org/html/2607.25973#S4.SS3)approaches two asK→∞K\\rightarrow\\infty\. It remains open whether some palette\-independent1<q<21<q<2is possible\. Therefore, currently, a recursive chain cannot discard the original palette and analyze only the current maximum list size: the algorithm must remember that every list is a subset of one fixed palettePP, whose size affects the running time\. The general reduction below is stated in exactly this fixed\-palette form and is thus sufficient forkk\-coloring, in which every subsequent instance is over the palette\[k\]\[k\], as well as for list\-coloring over a fixed palette—but not forkk\-list\-coloring over arbitrary palettes\.

## 5The general algorithm

We aim to generalize the reduction of Section[4](https://arxiv.org/html/2607.25973#S4)in a natural way: we fix a palette\[K\]\[K\], and construct a reduction from a sub\-2n2^\{n\}algorithm for\(k−1\)\(k\-1\)\-list\-coloring over\[K\]\[K\]to a sub\-2n2^\{n\}algorithm forkk\-list\-coloring over\[K\]\[K\], for all3≤k≤K3\\leq k\\leq K\. So far, we have constructed such reductions only forK−2≤k≤KK\-2\\leq k\\leq K\.

Cumbersome \(and many\) technical details aside, the warm\-up reduction can be described as follows: Unless the instance has an ‘easy’ structure we already have a fast solution for, we find in it many verticesvvthat have listsL​\(v\)L\(v\)of the maximum possible sizek=\(K−2\)k=\(K\-2\)and that also have many distinct neighbors whose correct color must be in the smaller complement listsQv=\[K\]∖L​\(v\)Q\_\{v\}=\[K\]\\setminus L\(v\)\. There, the size of these complements is\|Qv\|=2\|Q\_\{v\}\|=2\.

Then, we presented an algorithm to solve such instances with many size\-two lists: we picked a most common size\-two listQQ\. We then sped\-up the coloring of the graph by discarding the vertices with listQQand finding all subgraphs of the remaining graph using the sub\-palette\[K\]∖Q\[K\]\\setminus Q, and finally extending these solutions to the entire graph\.

While tempting to generalize just the first part and again encapsulate the second part into some natural black\-box statement, we are unable to do so\. Intuitively, it truly is not clear if list\-coloring instances with many lists of size three or four are easier to solve than general ones\. Instead, we take inspiration, or parts, from*both*components at the same time to construct the general reduction\.

When we construct the large set of vertices with maximum\-size listsL​\(v\)L\(v\)and the large set of their neighbors with complement listsQv=\[K\]∖L​\(v\)Q\_\{v\}=\[K\]\\setminus L\(v\), we already apply the observation used during the interpolation and restrict ourselves only to the most commonL​\(v\)L\(v\)\(and hence alsoQ=QvQ=Q\_\{v\}\)\. The sets remain large \(as in, of linear size innn\) as the palette is fixed and hence the number of different possible lists is bounded by a constant\. Now, we have a graph with many vertices that are forbidden from using colors in∅≠Q⊊\[K\]\\emptyset\\neq Q\\subsetneq\[K\], and also many vertices that are forced to use only colors fromQQ\. This now sounds reminiscent of the situation we tackle in the interpolation algorithm of Section[4\.3](https://arxiv.org/html/2607.25973#S4.SS3): There are\(1−ε\)​n\(1\-\\varepsilon\)nknown vertices \(for someε\>0\\varepsilon\>0\) which are a superset of the part of the graph that would eventually be colored by colors of\[K\]∖Q\[K\]\\setminus Q, and similarly, there are\(1−ε\)​n\(1\-\\varepsilon\)nvertices which are a superset of the part that would be colored by colors ofQQ\. Unlike Section[4\.3](https://arxiv.org/html/2607.25973#S4.SS3)though, “stitching” the two parts together – or finding which colorable subgraphs of each are compatible with each other – is significantly more difficult\. Fortunately, the machinery developed in\[[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8)\]solves*exactly*this problem; as discussed and cited in Lemma[3\.7](https://arxiv.org/html/2607.25973#S3.Thmtheorem7), we*are*able to solve that “stitching” problem in time comparable to enumerating over subsets of the two super\-sets separately\.

\(a\) Supported sets insideV​\(G\)V\(G\)𝒜Q:L​\(v\)⊆Q\\mathcal\{A\}\_\{Q\}:\\ L\(v\)\\subseteq QℬR:L​\(v\)⊆R\\mathcal\{B\}\_\{R\}:\\ L\(v\)\\subseteq R\(b\) Overlapping complements insideV​\(G\)V\(G\)V​\(G\)∖ℬRV\(G\)\\setminus\\mathcal\{B\}\_\{R\}QQ\-sideV​\(G\)∖𝒜QV\(G\)\\setminus\\mathcal\{A\}\_\{Q\}RR\-sidecomplementsR=\[K\]∖QR=\[K\]\\setminus QFigure 4:The same two boundaries in two views\. The supported sets𝒜Q\\mathcal\{A\}\_\{Q\}andℬR\\mathcal\{B\}\_\{R\}are exactly the two differences of the overlapping complementary domains shown on the right\.### 5\.1The fixed\-palette list\-to\-list bootstrap

We now make the preceding outline precise\. As in the warm\-up, a vertex is*active*when its list has the maximum currently allowed size, and goodness and badness are always defined relative to a fixed witness coloring\. The main new point is that, after choosing one common complementary setQQ, we preserve a linear set of active vertices with listR=P∖QR=P\\setminus Qwhile creating a second linear set whose lists are contained inQQ\. Corollary[3\.8](https://arxiv.org/html/2607.25973#S3.Thmtheorem8)then supplies the terminal algorithm\.

###### Theorem 5\.1\(General bootstrap\)\.

Fix a paletteP=\[K\]P=\[K\]and an integer3≤k≤K3\\leq k\\leq K\. If\(k−1\)\(k\-1\)\-list\-coloring overPPhas a randomized algorithm running inO∗​\(an\)O^\{\*\}\(a^\{n\}\)time for somea<2a<2, thenkk\-list\-coloring overPPhas a randomized algorithm running in

O∗​\(\(2−ε\)n\)O^\{\*\}\\bigl\(\(2\-\\varepsilon\)^\{n\}\\bigr\)time for someε\>0\\varepsilon\>0depending only onK,k,aK,k,a\. All failure probabilities may be madeexp⁡\(−Ω​\(n\)\)\\exp\(\-\\Omega\(n\)\)by repetition\.

###### Proof\.

We first consider the nonfinal casek<Kk<K\. Put

t:=K−k,M:=\(Kt\)\.t:=K\-k,\\qquad M:=\\binom\{K\}\{t\}\.Thus the complementQv=P∖L​\(v\)Q\_\{v\}=P\\setminus L\(v\)of every active list has sizett, and there are exactlyMMpossible complements\.

Apply Lemma[4\.1](https://arxiv.org/html/2607.25973#S4.Thmtheorem1)with the present values ofP,k,aP,k,a, and letβ0,Δ1,CS\\beta\_\{0\},\\Delta\_\{1\},C\_\{S\}be the constants it supplies\. Denote

γ:=β02​M,α:=γ2,p0:=γ8\.\\gamma:=\\frac\{\\beta\_\{0\}\}\{2M\},\\qquad\\alpha:=\\frac\{\\gamma\}\{2\},\\qquad p\_\{0\}:=\\frac\{\\gamma\}\{8\}\.Choose an integerr≥2r\\geq 2sufficiently large that

λ:=log2⁡\(1/p0\)r<1\.\\lambda:=\\frac\{\\log\_\{2\}\(1/p\_\{0\}\)\}\{r\}<1\.Finally, set

B:=k​Δ1,Δ:=r​\(1\+B\)\.B:=k\\Delta\_\{1\},\\qquad\\Delta:=r\(1\+B\)\.This order is important: the sampling sizerris fixed before the degree thresholdΔ\\Delta, and hence before we invoke the bounded\-degree algorithm\.

For a current instance onnnvertices, define the*easy solver*EEexactly as in the warm\-up\. If at leastα​n\\alpha nvertices have degree at mostΔ\\Delta, apply Theorem[3\.5](https://arxiv.org/html/2607.25973#S3.Thmtheorem5); otherwise apply the seed solver of Lemma[4\.1](https://arxiv.org/html/2607.25973#S4.Thmtheorem1)\. By a constant amount of amplification, there is a constant

such thatEEruns inO∗​\(Cn\)O^\{\*\}\(C^\{n\}\)time and succeeds with probability at least1/21/2, relative to every fixed witness coloring, whenever either

1. \(i\)at leastα​n\\alpha nvertices have degree at mostΔ\\Delta; or
2. \(ii\)at mostβ0​n\\beta\_\{0\}nactive vertices are bad\.

The algorithm can test condition \(i\), but it need not and cannot test condition \(ii\): when \(i\) fails, it simply runs the seed solver\.

Unlike the warm\-up, the hard part of the present algorithm applies only rule \(N\) from Lemma[3\.2](https://arxiv.org/html/2607.25973#S3.Thmtheorem2)\. In particular, singleton vertices are retained, so every current instance in a trial has the same numbernnof vertices as the original input\. For a fixedtt\-element setQ⊆PQ\\subseteq P, write

and, for an instanceII, define its two supported sets by

𝒜Q​\(I\):=\{u:LI​\(u\)⊆Q\},ℬR​\(I\):=\{u:LI​\(u\)⊆R\}\.\\mathcal\{A\}\_\{Q\}\(I\):=\\\{u:L\_\{I\}\(u\)\\subseteq Q\\\},\\qquad\\mathcal\{B\}\_\{R\}\(I\):=\\\{u:L\_\{I\}\(u\)\\subseteq R\\\}\.
The algorithm tries each of theMMpossible setsQQ\. AQQ\-specific trial starts from a fresh rule\-\(N\)\-normalized copy of the input, and every subroutine call and sample uses fresh independent randomness\. At each ofmmsteps, wheremmwill be fixed below, it does the following\.

1. \(1\)RunEEon a copy of the current instance\. If it finds a coloring, return it\.
2. \(2\)Abort the trial if\|ℬR​\(I\)\|<γ​n\\lvert\\mathcal\{B\}\_\{R\}\(I\)\\rvert<\\gamma n\. Otherwise choose a uniformly random vertexv∈V​\(G\)v\\in V\(G\), and abort unless LI​\(v\)=RanddegI⁡\(v\)\>Δ\.L\_\{I\}\(v\)=R\\qquad\\text\{and\}\\qquad\\deg\_\{I\}\(v\)\>\\Delta\.
3. \(3\)Choose a uniformly randomrr\-element setT⊆NI​\(v\)T\\subseteq N\_\{I\}\(v\), and simultaneously replace LI​\(u\)byLI​\(u\)∩Q\(∀u∈T\)\.L\_\{I\}\(u\)\\quad\\text\{by\}\\quad L\_\{I\}\(u\)\\cap Q\\qquad\(\\forall u\\in T\)\.Abort if an empty list is produced; otherwise exhaust normalization rule \(N\)\.

As before, a hard step that reaches the normalization at the end of step \(3\) is called*completed*\. Aftermmcompleted steps, the trial invokes Corollary[3\.8](https://arxiv.org/html/2607.25973#S3.Thmtheorem8)with the partitionP=Q∪˙RP=Q\\mathbin\{\\dot\{\\cup\}\}R\.

We next analyze the trial relative to a fixed witness coloringcc\. Suppose first that the initial instance satisfies neither easy condition\. It then has more thanβ0​n\\beta\_\{0\}nbad active vertices and fewer thanα​n\\alpha nvertices of degree at mostΔ\\Delta\. Hence more than\(β0−α\)​n\(\\beta\_\{0\}\-\\alpha\)nvertices are simultaneously bad, active, and of degree greater thanΔ\\Delta\. Pigeonholing theirMMpossible complements shows that somett\-setQQoccurs on at least

β0−αM​n≥β02​M​n=γ​n\\frac\{\\beta\_\{0\}\-\\alpha\}\{M\}n\\geq\\frac\{\\beta\_\{0\}\}\{2M\}n=\\gamma nof them\. Fix this choice ofQQ, putR=P∖QR=P\\setminus Q, and let𝒞\\mathcal\{C\}be a set of at leastγ​n\\gamma nsuch vertices\. Every vertex of𝒞\\mathcal\{C\}has list exactlyRR\.

Consider a successful trial in which every list restriction preservescc\. Every sampled neighbor \(in step \(3\)\) then has witness color inQQ, whereas every vertex of𝒞\\mathcal\{C\}has witness color inRR\. Consequently, no vertex of𝒞\\mathcal\{C\}is ever sampled as a neighbor in step \(3\), and its list remains exactlyRR\. Rule \(N\) only deletes edges, so every vertex of𝒞\\mathcal\{C\}also remains bad\. Thus the cardinality check in the beginning of step \(2\) always succeeds during this trial\. Moreover, whenever the low\-degree easy condition fails, fewer thanα​n\\alpha nvertices of the entire graph have degree at mostΔ\\Delta\. Therefore more than

\(γ−α\)​n=γ​n2\(\\gamma\-\\alpha\)n=\\frac\{\\gamma n\}\{2\}vertices of𝒞\\mathcal\{C\}still have degree greater thanΔ\\Deltaand are eligible choices forvv\.

Condition on choosing one of these eligible vertices\. Sincevvis bad andLI​\(v\)=RL\_\{I\}\(v\)=R, each of thekkcolors inRRoccurs on at mostΔ1\\Delta\_\{1\}neighbors ofvvundercc\. Hence at mostk​Δ1=Bk\\Delta\_\{1\}=Bneighbors have witness colors inRR; all other neighbors have witness colors inQQ\. Expose therrsampled neighbors one at a time\. Before each draw, at least

neighbors remain available, of which at mostBBhave witness colors outsideQQ\. Each draw therefore has conditional success probability at least1−1/r1\-1/r, and

Pr⁡\[c​\(T\)⊆Q\|v​is eligible\]≥\(1−1/r\)r≥14\.\\Pr\\\!\\left\[c\(T\)\\subseteq Q\\,\\middle\|\\,v\\text\{ is eligible\}\\right\]\\geq\(1\-1/r\)^\{r\}\\geq\\frac\{1\}\{4\}\.Together with the probability of choosing an eligible vertexvv, every hard step from a non\-easy witness\-compatible state preservesccwith probability at least

γ2⋅14=p0\.\\frac\{\\gamma\}\{2\}\\cdot\\frac\{1\}\{4\}=p\_\{0\}\.On this event no list becomes empty, so the step is completed\.

We now verify the deterministic progress made by*every*completed step, not only by the witness\-preserving ones\. Immediately before the step, rule \(N\) has been exhausted\. Thus, for everyu∈Tu\\in T, the edge\(u,v\)\(u,v\)and the equalityLI​\(v\)=RL\_\{I\}\(v\)=Rimply

LI​\(u\)∩R≠∅\.L\_\{I\}\(u\)\\cap R\\neq\\varnothing\.In particular,u∉𝒜Q​\(I\)u\\notin\\mathcal\{A\}\_\{Q\}\(I\)\. After the non\-trivial intersection in \(5\.7\), allrrsampled vertices belong to𝒜Q\\mathcal\{A\}\_\{Q\}\. Rule \(N\) then deletes every edge between aQQ\-supported vertex and anRR\-supported vertex, since their lists are disjoint\. A vertex created in one completed step can therefore never again be sampled from a vertexvvwhose list isRR\. Therrneighbors sampled in different completed steps are consequently distinct\.

The setℬR\\mathcal\{B\}\_\{R\}cannot decrease during a completed step either\. Indeed, sampling a vertex whose list is contained inRRwould make its intersection withQQempty and abort the trial; rule \(N\) does not change lists\. It follows that every trial reaching its terminal call satisfies

\|𝒜Q​\(Im\)\|≥r​m,\|ℬR​\(Im\)\|≥γ​n\.\\lvert\\mathcal\{A\}\_\{Q\}\(I\_\{m\}\)\\rvert\\geq rm,\\qquad\\lvert\\mathcal\{B\}\_\{R\}\(I\_\{m\}\)\\rvert\\geq\\gamma n\.Corollary[3\.8](https://arxiv.org/html/2607.25973#S3.Thmtheorem8)therefore solves the terminal instance in

O∗​\(2n−r​m\+2n−γ​n\)O^\{\*\}\\bigl\(2^\{n\-rm\}\+2^\{n\-\\gamma n\}\\bigr\)time\. Notice that these are worst\-case bounds for every nonaborting terminal call; they do not rely on the trial having preservedcc\.

It remains to choose the numbermmof steps in each trial\. Afterκ:=log2⁡C<1\\kappa:=\\log\_\{2\}C<1has been fixed, put

d:=min⁡\{γ2,1−κ2​λ\}\>0,m:=⌊d​nr⌋\.d:=\\min\\left\\\{\\frac\{\\gamma\}\{2\},\\frac\{1\-\\kappa\}\{2\\lambda\}\\right\\\}\>0,\\qquad m:=\\left\\lfloor\\frac\{dn\}\{r\}\\right\\rfloor\.Ifm=0m=0, thenn<r/dn<r/d, sonnis bounded by a constant depending only on the fixed parameters and the instance may be solved by exhaustive search\. We henceforth assumem≥1m\\geq 1\.

To prove the success probability, call a current state*witness\-compatible*if every current list contains the color assigned bycc\. We claim by \(backward\) induction that, from a witness\-compatible state withhhhard steps remaining, the rest of the trial succeeds with probability at least

12​p0h\.\\frac\{1\}\{2\}p\_\{0\}^\{h\}\.Forh=0h=0, the exact two\-block terminal succeeds with probability one\. Leth≥1h\\geq 1\. If the current state is easy, the call toEEsucceeds with probability at least1/21/2, which is at least12​p0h\\frac\{1\}\{2\}p\_\{0\}^\{h\}\. If the state is not easy, then, conditional on the failure ofEE, the next hard step preserves the witness with probability at leastp0p\_\{0\}, after which the induction hypothesis applies\. More explicitly, ifsEs\_\{E\}is the probability thatEEsucceeds andx=12​p0hx=\\frac\{1\}\{2\}p\_\{0\}^\{h\}, the total success probability is at least

sE\+\(1−sE\)​x≥x\.s\_\{E\}\+\(1\-s\_\{E\}\)x\\geq x\.
Thus, for the favorable choice ofQQ, one trial succeeds with probability at least12​p0m\\frac\{1\}\{2\}p\_\{0\}^\{m\}\. If the initial state was already easy, the first call toEEgives at least the same success probability lower bound for every choice ofQQ\. For eachQQ, run

Ntr:=⌈2​np0m⌉N\_\{\\mathrm\{tr\}\}:=\\left\\lceil\\frac\{2n\}\{p\_\{0\}^\{m\}\}\\right\\rceilindependent trials\. On a yes\-instance, the probability that all trials for a favorableQQfail is at most

\(1−12​p0m\)Ntr≤e−n\.\\left\(1\-\\frac\{1\}\{2\}p\_\{0\}^\{m\}\\right\)^\{N\_\{\\mathrm\{tr\}\}\}\\leq e^\{\-n\}\.
We finally bound the running time\. Since

p0−m≤2\(d​n/r\)​log2⁡\(1/p0\)=2λ​d​n,p\_\{0\}^\{\-m\}\\leq 2^\{\(dn/r\)\\log\_\{2\}\(1/p\_\{0\}\)\}=2^\{\\lambda dn\},amplifying all easy calls gives base\-two exponent at most

κ\+λ​d≤κ\+1−κ2=1\+κ2<1\.\\kappa\+\\lambda d\\leq\\kappa\+\\frac\{1\-\\kappa\}\{2\}=\\frac\{1\+\\kappa\}\{2\}<1\.Alsor​m≥d​n−rrm\\geq dn\-r, so the fixed factor2r2^\{r\}absorbs the rounding in the first term of the terminal bound\. After amplification, the two terminal terms have exponents at most

1−d\+λ​d=1−\(1−λ\)​d<11\-d\+\\lambda d=1\-\(1\-\\lambda\)d<1and

1−γ\+λ​d≤1−γ\+λ​γ2<1,1\-\\gamma\+\\lambda d\\leq 1\-\\gamma\+\\frac\{\\lambda\\gamma\}\{2\}<1,respectively\. The numberMMof choices ofQQ, the number of easy calls within one trial, and all hard steps contribute only polynomial or constant factors outside these exponents\. Consequently, for

ρ:=max⁡\{κ\+λ​d,1−\(1−λ\)​d,1−γ\+λ​d\}<1,\\rho:=\\max\\bigl\\\{\\kappa\+\\lambda d,\\,1\-\(1\-\\lambda\)d,\\,1\-\\gamma\+\\lambda d\\bigr\\\}<1,the running time isO∗​\(2ρ​n\)O^\{\*\}\(2^\{\\rho n\}\), equivalentlyO∗​\(\(2−ε\)n\)O^\{\*\}\(\(2\-\\varepsilon\)^\{n\}\)forε=2−2ρ\>0\\varepsilon=2\-2^\{\\rho\}\>0\.

Every acceptance is sound as it is verifiable, and thus amplification is always possible\.

It remains to handle the final casek=Kk=K, where an active list is the entire palette and has empty complement\. Apply Lemma[4\.1](https://arxiv.org/html/2607.25973#S4.Thmtheorem1)as above, set

α:=β02,Δ:=K​Δ1,\\alpha:=\\frac\{\\beta\_\{0\}\}\{2\},\\qquad\\Delta:=K\\Delta\_\{1\},and defineEEfrom the low\-degree and seed solvers\. After constant amplification,EEruns inO∗​\(Cn\)O^\{\*\}\(C^\{n\}\)time for someC<2C<2and succeeds with probability at least1/21/2whenever either easy condition holds\. Relative to a fixed witness coloring, every bad active vertex satisfies

deg⁡\(v\)=∑q∈P\|N​\(v\)∩c−1​\(q\)\|≤K​Δ1=Δ\.\\deg\(v\)=\\sum\_\{q\\in P\}\\bigl\|N\(v\)\\cap c^\{\-1\}\(q\)\\bigr\|\\leq K\\Delta\_\{1\}=\\Delta\.If there are at mostβ0​n\\beta\_\{0\}nbad active vertices, the seed condition holds\. Otherwise more thanβ0​n\>α​n\\beta\_\{0\}n\>\\alpha nvertices have degree at mostΔ\\Delta, so the low\-degree condition holds\. Hence every colorable instance is easy\. RepeatingEE2​n2ntimes reduces its false\-negative probability toexp⁡\(−Ω​\(n\)\)\\exp\(\-\\Omega\(n\)\), while preserving a base smaller than two\. This proves the theorem\. ∎

For completeness, Algorithm[3](https://arxiv.org/html/2607.25973#algorithm3)gives the entire reduction\. Calls to the seed solver, the bounded\-degree solver, and the two\-block algorithm are left as the named black boxes already analyzed above; the sampling and list modifications are shown explicitly\.

Input:A list\-coloring instance

I=\(G,L\)I=\(G,L\)over

P=\[K\]P=\[K\], with

\|L​\(v\)\|≤k\|L\(v\)\|\\leq kfor every

vv
Output:

𝖸𝖤𝖲\\mathsf\{YES\}or

𝖭𝖮\\mathsf\{NO\}
Let the constants be those fixed in the proof of Theorem[5\.1](https://arxiv.org/html/2607.25973#S5.Thmtheorem1);

I0←Normalize\-\(N\)​\(I\)I\_\{0\}\\leftarrow\\textsc\{Normalize\-\(N\)\}\(I\);

if*V​\(I0\)=∅V\(I\_\{0\}\)=\\varnothing*then

return

𝖸𝖤𝖲\\mathsf\{YES\};

if*k=Kk=K*then

for*j←1j\\leftarrow 1to2​n2n*do

if**EasySolver\-*​E​\(I0\)\\textsc\{EasySolver\-\}E\(I\_\{0\}\)finds a coloring*then

return

𝖸𝖤𝖲\\mathsf\{YES\};

return

𝖭𝖮\\mathsf\{NO\};

t←K−kt\\leftarrow K\-k;

if*m=0m=0*then

return

ExhaustiveListColoring​\(I0\)\\textsc\{ExhaustiveListColoring\}\(I\_\{0\}\);

foreach*Q⊆PQ\\subseteq Pwith\|Q\|=t\|Q\|=t*do

R←P∖QR\\leftarrow P\\setminus Q;

for*j←1j\\leftarrow 1toNtrN\_\{\\mathrm\{tr\}\}*do

J←I0J\\leftarrow I\_\{0\};

for*i←1i\\leftarrow 1tomm*do

if**EasySolver\-*​E​\(J\)\\textsc\{EasySolver\-\}E\(J\)finds a coloring*then

return

𝖸𝖤𝖲\\mathsf\{YES\};

ℬR←\{u∈V​\(J\):LJ​\(u\)⊆R\}\\mathcal\{B\}\_\{R\}\\leftarrow\\\{u\\in V\(J\):L\_\{J\}\(u\)\\subseteq R\\\};

if*\|ℬR\|<γ​n\|\\mathcal\{B\}\_\{R\}\|<\\gamma n*then

continue with the next trial;

Choose

vvuniformly at random from

V​\(J\)V\(J\);

if*LJ​\(v\)≠RL\_\{J\}\(v\)\\neq RordegJ⁡\(v\)≤Δ\\deg\_\{J\}\(v\)\\leq\\Delta*then

continue with the next trial;

Choose a uniformly random

rr\-element set

T⊆NJ​\(v\)T\\subseteq N\_\{J\}\(v\);

Simultaneously replace

LJ​\(u\)L\_\{J\}\(u\)by

LJ​\(u\)∩QL\_\{J\}\(u\)\\cap Qfor every

u∈Tu\\in T;

if*one of the resulting lists is empty*then

continue with the next trial;

J←Normalize\-\(N\)​\(J\)J\\leftarrow\\textsc\{Normalize\-\(N\)\}\(J\);

if**TwoBlockListColoring*​\(J;Q,R\)\\textsc\{TwoBlockListColoring\}\(J;Q,R\)returns𝖸𝖤𝖲\\mathsf\{YES\}*then

return

𝖸𝖤𝖲\\mathsf\{YES\};

return

𝖭𝖮\\mathsf\{NO\};

Algorithm 3The fixed\-palette list\-to\-list bootstrapWe finally deduce as a corollary our main theorem\.

###### Theorem 5\.2\(Fixed\-palette List Coloring\)\.

For every fixed integerK≥1K\\geq 1, there is anεK\>0\\varepsilon\_\{K\}\>0such that list\-coloring over the paletteP=\[K\]P=\[K\]can be solved with exponentially small one\-sided error in

O∗​\(\(2−εK\)n\)O^\{\*\}\\bigl\(\(2\-\\varepsilon\_\{K\}\)^\{n\}\\bigr\)time\. In particular,KK\-coloring admits the same running\-time bound\.

###### Proof\.

ForK≤2K\\leq 2, list\-coloring overPPis polynomial\-time solvable by 2\-SAT\[[APT79](https://arxiv.org/html/2607.25973#bib.bib1)\]\. LetK≥3K\\geq 3\. The same reduction gives a polynomial\-time algorithm for22\-list\-coloring overP=\[K\]P=\[K\]\. Apply Theorem[5\.1](https://arxiv.org/html/2607.25973#S5.Thmtheorem1)successively for

k=3,4,…,K\.k=3,4,\\ldots,K\.At each iteration the palette remains the same fixed setPP, so the output algorithm at one level satisfies precisely the hypothesis needed at the next\. Atk=Kk=K, every nonempty list contained inPPhas size at mostKK, and hence the resulting algorithm solves arbitrary list\-coloring overPP\. TakingL​\(v\)=PL\(v\)=Pfor every vertex gives ordinaryKK\-coloring\. ∎

We remark that ordinaryKK\-coloring is the special caseL​\(v\)=PL\(v\)=Pfor every vertex\. Conversely, list coloring over a palette of sizeKKreduces toKK\-coloring by adding aKK\-clique representing the colors and joining each vertex to the clique vertices corresponding to its forbidden colors\. Thus, for fixedKK, the two formulations are equivalent up toKKadditional vertices\.

## 6Plucking up the courage to specify the constants

Throughout the paper, we focused on the existence of a positiveεK\\varepsilon\_\{K\}for Theorem[5\.2](https://arxiv.org/html/2607.25973#S5.Thmtheorem2); we did not, on the other hand, carry any quantitative estimates between steps of the overall algorithm or reductions\. Due to the extensive number of ‘moving parts’ and choices of constants throughout the algorithms, as well as these quantitative bounds being rather grim anyway, this choice was useful for readability\. In this section, we repeat and revisit the overall analysis, somewhat informally, to present loose bounds for the asymptotic behavior ofεK\\varepsilon\_\{K\}as given by our algorithm without further optimizations\. This section is thus unnecessary for any of the statements or proofs in the paper\. Our only purpose here is to give the adventurous reader a sense of whatεK\\varepsilon\_\{K\}is guaranteed by this work, as well as present an explicit baseline for future improvements\. Proceed at your own risk\.

Our bookkeeping shows that the savingεK\\varepsilon\_\{K\}is roughly described by the reciprocal of a tower of exponentials of heightΘ​\(K\)\\Theta\(K\)\. We make no attempt to optimize the choice of constants\. The main loss comes from repeatedly invoking the low\-degree algorithm of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]\. That algorithm in turn uses the subset\-removal lemma of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7), Theorem 1\.8\]\. As with many removal\- and regularity\-type combinatorial arguments, the dependence supplied by that lemma is enormous\. At every list\-size level, the saving inherited from the preceding level determines a degree threshold; the removal lemma is then applied at that threshold, and the saving proved from it is doubly exponentially smaller\. Iterating over the list sizes is what produces the tower behavior\.

### 6\.1The seed solver

Fix a paletteP=\[K\]P=\[K\], and consider one step from\(k−1\)\(k\-1\)\-list\-coloring tokk\-list\-coloring overPP\. Suppose that the algorithm already constructed for\(k−1\)\(k\-1\)\-list\-coloring runs in

O∗​\(2\(1−η\)​n\),a:=21−η,O^\{\*\}\\\!\\left\(2^\{\(1\-\\eta\)n\}\\right\),\\qquad a:=2^\{1\-\\eta\},where0<η≤10<\\eta\\leq 1\. The saving in the ordinary exponential base is

2−a=2​\(1−2−η\)=Θ​\(η\),2\-a=2\\bigl\(1\-2^\{\-\\eta\}\\bigr\)=\\Theta\(\\eta\),so it suffices to follow the base\-two exponent savingη\\eta\.

We briefly recall the two parameters appearing in the seed solver of Lemma[4\.1](https://arxiv.org/html/2607.25973#S4.Thmtheorem1)\. The parameterΔ1\\Delta\_\{1\}is the threshold in the definition of a good active vertex: such a vertex has more thanΔ1\\Delta\_\{1\}neighbors receiving one common color in the fixed witness coloring\. The parameterβ0\\beta\_\{0\}is the fraction of active vertices that may be bad while the seed solver is still guaranteed to succeed\. Writing

H:=log⁡\(K/a\)=Θ​\(log⁡K\),H:=\\log\(K/a\)=\\Theta\(\\log K\),the analysis of Lemma[4\.1](https://arxiv.org/html/2607.25973#S4.Thmtheorem1)gives the seed solver base\-two exponent

1−η\+\(4​ln⁡Δ1\+1Δ1\+β0\)​H\.1\-\\eta\+\\left\(4\\frac\{\\ln\\Delta\_\{1\}\+1\}\{\\Delta\_\{1\}\}\+\\beta\_\{0\}\\right\)H\.We therefore set

β0:=η4​H\\beta\_\{0\}:=\\frac\{\\eta\}\{4H\}and chooseΔ1\\Delta\_\{1\}to be the least sufficiently large integer satisfying

4​H​ln⁡Δ1\+1Δ1≤η4\.4H\\frac\{\\ln\\Delta\_\{1\}\+1\}\{\\Delta\_\{1\}\}\\leq\\frac\{\\eta\}\{4\}\.The seed solver then has exponent at most1−η/21\-\\eta/2, and the parameters have the scales

β0=Θ​\(ηlog⁡K\),Δ1=Θ​\(log⁡Kη​log⁡log⁡Kη\)\.\\beta\_\{0\}=\\Theta\\\!\\left\(\\frac\{\\eta\}\{\\log K\}\\right\),\\qquad\\Delta\_\{1\}=\\Theta\\\!\\left\(\\frac\{\\log K\}\{\\eta\}\\log\\frac\{\\log K\}\{\\eta\}\\right\)\.We shall also use the immediate lower bound

Δ1≥16​Hη=Ω​\(log⁡Kη\)\.\\Delta\_\{1\}\\geq\\frac\{16H\}\{\\eta\}=\\Omega\\\!\\left\(\\frac\{\\log K\}\{\\eta\}\\right\)\.

### 6\.2One bootstrap step

#### Finding one common missing\-color set\.

First suppose thatk<Kk<K\. An active list has a complement of sizeK−kK\-k, so the number of possible complements is

M:=\(KK−k\)\.M:=\\binom\{K\}\{K\-k\}\.If the seed solver is not guaranteed to succeed, more thanβ0​n\\beta\_\{0\}nactive vertices are bad\. As in the proof of Theorem[5\.1](https://arxiv.org/html/2607.25973#S5.Thmtheorem1), set

γ:=β02​M,α:=γ2\.\\gamma:=\\frac\{\\beta\_\{0\}\}\{2M\},\\qquad\\alpha:=\\frac\{\\gamma\}\{2\}\.Hereα​n\\alpha nis the threshold for invoking the low\-degree algorithm, whileγ​n\\gamma nis the number of bad high\-degree vertices that can be guaranteed to share one list complementQQ\. Indeed, after discarding fewer thanα​n\\alpha nlow\-degree vertices, pigeonholing among theMMpossible complements leaves at leastγ​n\\gamma nvertices with one common complement\. Consequently,

γ,α=Θ​\(ηM​log⁡K\)\.\\gamma,\\alpha=\\Theta\\\!\\left\(\\frac\{\\eta\}\{M\\log K\}\\right\)\.

#### One witness\-preserving hard step\.

Fix the common complementQQ, and writeR=P∖QR=P\\setminus Q\. A hard step chooses a high\-degree bad vertexvvwith listRRand restrictsrrof its neighbors to colors inQQ\. Whenever the low\-degree condition fails, the probability of choosing an eligible vertex is at leastγ/2\\gamma/2\. Moreover, sincevvis bad, at most

of its neighbors receive witness colors inRR\. ThusBBis the number of neighbors that the sampling must avoid\.

We then set

p0:=γ8,r:=max⁡\{2,⌈2​log⁡\(1/p0\)⌉\},λ:=log⁡\(1/p0\)r,p\_\{0\}:=\\frac\{\\gamma\}\{8\},\\qquad r:=\\max\\left\\\{2,\\left\\lceil 2\\log\(1/p\_\{0\}\)\\right\\rceil\\right\\\},\\qquad\\lambda:=\\frac\{\\log\(1/p\_\{0\}\)\}\{r\},and take the degree threshold to be

Δ:=r​\(1\+B\)=r​\(1\+k​Δ1\)\.\\Delta:=r\(1\+B\)=r\(1\+k\\Delta\_\{1\}\)\.The role ofrris to amortize the repetition cost: the choice above ensuresλ≤1/2\\lambda\\leq 1/2\. The role ofΔ\\Deltais to ensure that, whenrrneighbors are sampled without replacement, every draw avoids the at mostBBwitness\-incompatible neighbors with conditional probability at least1−1/r1\-1/r\. Hence allrrrestrictions preserve the witness with probability at least\(1−1/r\)r≥1/4\(1\-1/r\)^\{r\}\\geq 1/4, and a complete hard step preserves it with probability at leastp0p\_\{0\}\.

Since

p0=Θ​\(ηM​log⁡K\),p\_\{0\}=\\Theta\\\!\\left\(\\frac\{\\eta\}\{M\\log K\}\\right\),we have

r=O​\(log⁡M\+log⁡log⁡K\+log⁡\(1/η\)\)\.r=O\\\!\\left\(\\log M\+\\log\\log K\+\\log\(1/\\eta\)\\right\)\.Combining this with the estimate forΔ1\\Delta\_\{1\}, and usingM≤2KM\\leq 2^\{K\}andk≤Kk\\leq K, gives

Ω​\(1/η\)≤Δ≤\(Kη\)O​\(1\)\.\\Omega\(1/\\eta\)\\leq\\Delta\\leq\\left\(\\frac\{K\}\{\\eta\}\\right\)^\{O\(1\)\}\.Only these two estimates on the degree threshold will matter below\.

#### The final level\.

Whenk=Kk=K, an active list is the entire palette, and there is no nonempty complementQQor hard sampling phase\. The parameters used by the easy solver are then

α:=β02,Δ:=K​Δ1\.\\alpha:=\\frac\{\\beta\_\{0\}\}\{2\},\\qquad\\Delta:=K\\Delta\_\{1\}\.Every bad active vertex has degree at mostΔ\\Delta\. Thus either the seed solver applies, or more thanα​n\\alpha nvertices satisfy the low\-degree condition\. At this level as well,

α=Ω​\(η2K​log⁡K\),Ω​\(1/η\)≤Δ≤\(Kη\)O​\(1\)\.\\alpha=\\Omega\\\!\\left\(\\frac\{\\eta\}\{2^\{K\}\\log K\}\\right\),\\qquad\\Omega\(1/\\eta\)\\leq\\Delta\\leq\\left\(\\frac\{K\}\{\\eta\}\\right\)^\{O\(1\)\}\.

#### The saving supplied by the low\-degree solver\.

It remains to estimate the saving obtained when at leastα​n\\alpha nvertices have degree at mostΔ\\Delta\. Put

zΔ:=−ln⁡\(1−2−\(Δ\+1\)\)\.z\_\{\\Delta\}:=\-\\ln\\bigl\(1\-2^\{\-\(\\Delta\+1\)\}\\bigr\)\.The quantitative bounds in the low\-degree algorithm of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7), Sections 4\.3 and 5\]give a base\-two exponent saving of at least a universal constant times

gLD:=α​zΔΔ​\(Δ\+1\)​exp⁡\(−Δ2​ln⁡kzΔ\)\.g\_\{\\mathrm\{LD\}\}:=\\frac\{\\alpha z\_\{\\Delta\}\}\{\\Delta\(\\Delta\+1\)\}\\exp\\\!\\left\(\-\\frac\{\\Delta^\{2\}\\ln k\}\{z\_\{\\Delta\}\}\\right\)\.This follows by substituting

\|S\|≥α​nΔ\+1,Crem=ln⁡kzΔ,ρ​\(Δ,Crem\)\>1Δ​exp⁡\(1\+Crem​Δ2\)\|S\|\\geq\\frac\{\\alpha n\}\{\\Delta\+1\},\\qquad C\_\{\\mathrm\{rem\}\}=\\frac\{\\ln k\}\{z\_\{\\Delta\}\},\\qquad\\rho\(\\Delta,C\_\{\\mathrm\{rem\}\}\)\>\\frac\{1\}\{\\Delta\\exp\(1\+C\_\{\\mathrm\{rem\}\}\\Delta^\{2\}\)\}into the running\-time bound proved there\.

NowzΔ=Θ​\(2−Δ\)z\_\{\\Delta\}=\\Theta\(2^\{\-\\Delta\}\)\. Together with

α=Ω​\(η2K​log⁡K\)andΩ​\(1/η\)≤Δ≤\(K/η\)O​\(1\),\\alpha=\\Omega\\\!\\left\(\\frac\{\\eta\}\{2^\{K\}\\log K\}\\right\)\\quad\\text\{and\}\\quad\\Omega\(1/\\eta\)\\leq\\Delta\\leq\(K/\\eta\)^\{O\(1\)\},this gives

2−2\(K/η\)O​\(1\)≤gLD≤2−2Ω​\(1/η\)\.2^\{\-\\,2^\{\(K/\\eta\)^\{O\(1\)\}\}\}\\leq g\_\{\\mathrm\{LD\}\}\\leq 2^\{\-\\,2^\{\\Omega\(1/\\eta\)\}\}\.This is the doubly exponential loss responsible for the final tower\.

#### Combining the costs of the step\.

Let2κ<22^\{\\kappa\}<2be the base of the easy solver obtained by combining the seed and low\-degree alternatives\. Its exponent saving satisfies

1−κ=Θ​\(min⁡\{η,gLD\}\)\.1\-\\kappa=\\Theta\\\!\\left\(\\min\\\{\\eta,g\_\{\\mathrm\{LD\}\}\\\}\\right\)\.The remaining parameterddspecifies the linear number of vertices that the hard steps place on theQQ\-side before the terminal two\-block call\. As in the proof of Theorem[5\.1](https://arxiv.org/html/2607.25973#S5.Thmtheorem1), take

d:=min⁡\{γ2,1−κ2​λ\}\.d:=\\min\\left\\\{\\frac\{\\gamma\}\{2\},\\frac\{1\-\\kappa\}\{2\\lambda\}\\right\\\}\.The first term ensures that the second side of the terminal instance also remains linear, while the second ensures that the repetition factor2λ​d​n2^\{\\lambda dn\}consumes at most half of the easy solver’s exponent saving\. The three terms in the running\-time analysis of the bootstrap then give a new exponent saving

ηnew=Θ​\(min⁡\{γ,η,gLD\}\)\.\\eta\_\{\\mathrm\{new\}\}=\\Theta\\\!\\left\(\\min\\\{\\gamma,\\eta,g\_\{\\mathrm\{LD\}\}\\\}\\right\)\.Since

γ=Θ​\(ηM​log⁡K\)≥η​2−O​\(K\),\\gamma=\\Theta\\\!\\left\(\\frac\{\\eta\}\{M\\log K\}\\right\)\\geq\\eta\\,2^\{\-O\(K\)\},the low\-degree term is the asymptotically dominant loss\. For a suitable explicit choice of the constants hidden above,

2−2\(K/η\)O​\(1\)≤ηnew≤2−2Ω​\(1/η\)\.2^\{\-\\,2^\{\(K/\\eta\)^\{O\(1\)\}\}\}\\leq\\eta\_\{\\mathrm\{new\}\}\\leq 2^\{\-\\,2^\{\\Omega\(1/\\eta\)\}\}\.The final level, which has no hard sampling phase, obeys the same estimate\.

### 6\.3Iterating over all list sizes

Forh≥0h\\geq 0, define

Tower0⁡\(x\):=x,Towerh\+1⁡\(x\):=2Towerh⁡\(x\)\.\\operatorname\{Tower\}\_\{0\}\(x\):=x,\\qquad\\operatorname\{Tower\}\_\{h\+1\}\(x\):=2^\{\\operatorname\{Tower\}\_\{h\}\(x\)\}\.Fix a universal constantc0\>0c\_\{0\}\>0small enough for the running\-time analysis above\. At every nonfinal level, define

ηk\+1:=c0min\{γk\+1,ηk,gLD,k\+1\},\\eta\_\{k\+1\}:=c\_\{0\}\\min\\\{\\gamma\_\{k\+1\},\\eta\_\{k\},g\_\{\\mathrm\{LD\},k\+1\}\\\},whereγk\+1\\gamma\_\{k\+1\}andgLD,k\+1g\_\{\\mathrm\{LD\},k\+1\}are the values ofγ\\gammaandgLDg\_\{\\mathrm\{LD\}\}in the step constructing the\(k\+1\)\(k\+1\)\-list\-coloring algorithm\. At the final level, where there is no hard sampling phase, omitγk\+1\\gamma\_\{k\+1\}from the minimum\. Thusηk\\eta\_\{k\}is an exponent saving for the algorithm constructed forkk\-list\-coloring over the fixed palette\[K\]\[K\]\. We start withη2=1\\eta\_\{2\}=1, since22\-list\-coloring is solvable in polynomial time, and put

xk:=1ηk\.x\_\{k\}:=\\frac\{1\}\{\\eta\_\{k\}\}\.The estimate for one bootstrap step implies that there are universal constantsc\>0c\>0andD≥1D\\geq 1such that

22c​xk≤xk\+1≤22\(K​xk\)D\.2^\{\\,2^\{cx\_\{k\}\}\}\\leq x\_\{k\+1\}\\leq 2^\{\\,2^\{\(Kx\_\{k\}\)^\{D\}\}\}\.
We first derive the lower bound onxKx\_\{K\}\. Choose a universal constantx0x\_\{0\}such that

2c​x≥xfor every​x≥x0\.2^\{cx\}\\geq x\\qquad\\text\{for every \}x\\geq x\_\{0\}\.Starting fromx2=1x\_\{2\}=1, the lower recurrence reachesx0x\_\{0\}after a universal number of steps\. At every subsequent level,

xk\+1≥22c​xk≥2xk\.x\_\{k\+1\}\\geq 2^\{\\,2^\{cx\_\{k\}\}\}\\geq 2^\{x\_\{k\}\}\.Iterating this inequality through the remaining list sizes gives

xK≥TowerK−O​\(1\)⁡\(2\)\.x\_\{K\}\\geq\\operatorname\{Tower\}\_\{K\-O\(1\)\}\(2\)\.
For the reverse direction, fix a sufficiently large universal integerAA, and set

hk:=A​K\+3​\(k−2\)\.h\_\{k\}:=AK\+3\(k\-2\)\.We claim inductively that

xk≤Towerhk⁡\(2\)\.x\_\{k\}\\leq\\operatorname\{Tower\}\_\{h\_\{k\}\}\(2\)\.The claim is immediate fork=2k=2\. Suppose it holds at levelkk, and writey=Towerhk⁡\(2\)y=\\operatorname\{Tower\}\_\{h\_\{k\}\}\(2\)\. Sincehk≥A​Kh\_\{k\}\\geq AK, the constantAAmay be chosen so thaty≥Ky\\geq Kand

\(K​xk\)D≤\(K​y\)D≤y2​D≤2y=Towerhk\+1⁡\(2\)\.\(Kx\_\{k\}\)^\{D\}\\leq\(Ky\)^\{D\}\\leq y^\{2D\}\\leq 2^\{y\}=\\operatorname\{Tower\}\_\{h\_\{k\}\+1\}\(2\)\.The upper recurrence now gives

xk\+1≤22Towerhk\+1⁡\(2\)=Towerhk\+3⁡\(2\)=Towerhk\+1⁡\(2\)\.x\_\{k\+1\}\\leq 2^\{\\,2^\{\\operatorname\{Tower\}\_\{h\_\{k\}\+1\}\(2\)\}\}=\\operatorname\{Tower\}\_\{h\_\{k\}\+3\}\(2\)=\\operatorname\{Tower\}\_\{h\_\{k\+1\}\}\(2\)\.In particular,

xK≤TowerA​K\+3​\(K−2\)⁡\(2\)≤Tower\(A\+3\)​K⁡\(2\)\.x\_\{K\}\\leq\\operatorname\{Tower\}\_\{AK\+3\(K\-2\)\}\(2\)\\leq\\operatorname\{Tower\}\_\{\(A\+3\)K\}\(2\)\.
We finally note that

xK2​ln⁡2≤1εK≤xK\.\\frac\{x\_\{K\}\}\{2\\ln 2\}\\leq\\frac\{1\}\{\\varepsilon\_\{K\}\}\\leq x\_\{K\}\.
This proves the following\.

###### Proposition 6\.1\(Quantitative estimate\)\.

There are universal constantsC1,C2\>0C\_\{1\},C\_\{2\}\>0such that, for every sufficiently largeKK,

Tower⌊C1​K⌋⁡\(2\)≤1εK≤Tower⌈C2​K⌉⁡\(2\)\.\\operatorname\{Tower\}\_\{\\lfloor C\_\{1\}K\\rfloor\}\(2\)\\leq\\frac\{1\}\{\\varepsilon\_\{K\}\}\\leq\\operatorname\{Tower\}\_\{\\lceil C\_\{2\}K\\rceil\}\(2\)\.In particular, the reciprocal of the saving obtained above has tower heightΘ​\(K\)\\Theta\(K\)\.

## 7Discussion and open problems

Our main contribution is a resolution to the long\-standing natural question about the exact running times of graph coloring algorithms; we showed that for anyk∈ℕk\\in\\mathbb\{N\}there existsεk\>0\\varepsilon\_\{k\}\>0such thatkk\-coloring can be solved in\(2−εk\)n\(2\-\\varepsilon\_\{k\}\)^\{n\}time\. This comes in comparison to theO∗​\(2n\)O^\{\*\}\(2^\{n\}\)time algorithm that generally computes the chromatic number of a graph\.

The most immediate quantitative problem is to improve the asymptotic behavior ofεk\\varepsilon\_\{k\}\. Forkk\-SAT, which exhibits a similar behavior \(general SAT has aO∗​\(2n\)O^\{\*\}\(2^\{n\}\)time algorithm while every fixedkk\-SAT has an algorithm running in\(2−εk′\)n\(2\-\\varepsilon^\{\\prime\}\_\{k\}\)^\{n\}time\), an extensive body of works accumulated across decades to improve the constantsεk′\\varepsilon^\{\\prime\}\_\{k\}or conjecture their asymptotic behavior\[[MS85](https://arxiv.org/html/2607.25973#bib.bib14),[ROD96](https://arxiv.org/html/2607.25973#bib.bib20),[PPZ99](https://arxiv.org/html/2607.25973#bib.bib15),[PPS\+05](https://arxiv.org/html/2607.25973#bib.bib17),[SCH99](https://arxiv.org/html/2607.25973#bib.bib10),[HER14b](https://arxiv.org/html/2607.25973#bib.bib11),[HER14a](https://arxiv.org/html/2607.25973#bib.bib12),[SS17](https://arxiv.org/html/2607.25973#bib.bib21),[HKZ\+19](https://arxiv.org/html/2607.25973#bib.bib22),[IP01](https://arxiv.org/html/2607.25973#bib.bib13)\]\. We expect a similar progress to now be possible forkk\-coloring\. The reciprocal\-tower estimate in Section[6](https://arxiv.org/html/2607.25973#S6)seems unlikely, or at least currently unjustified, to describe the intrinsic complexity ofkk\-coloring\.

The second concrete question concerns the generalization of our result to list\-coloring\. We already show that list\-coloring instances over a fixed\-size palettePPcan be solved in time\(2−ε\|P\|\)n\(2\-\\varepsilon\_\{\|P\|\}\)^\{n\}for someε\|P\|\>0\\varepsilon\_\{\|P\|\}\>0\. Plausibly, a similar result can be obtained forkk\-list\-coloring whenkkis fixed but the palette is unbounded\.

What seems to be the first obstruction preventing our techniques from extending to a palette\-independent settings, is the binary interpolation algorithm\. Ifbbof thennvertices have lists of size at most two, what is the smallest palette\-independentq∈\(1,2\)q\\in\(1,2\)for which one can achieve running time

O∗​\(2n−b​qb\)​?O^\{\*\}\\bigl\(2^\{n\-b\}q^\{b\}\\bigr\)?Theorem[4\.4](https://arxiv.org/html/2607.25973#S4.Thmtheorem4)givesqK=21−1/\(K2\)q\_\{K\}=2^\{1\-1/\\binom\{K\}\{2\}\}on a palette of sizeKK\. Under ETH, we excludedq=1q=1\. Is there a palette\-independent constantq<2q<2? A positive answer would simplify the warm\-up reductions and could be the missing component to avoid the palette dependence of the full construction\.

Two further natural questions are whether the randomization can be removed and whether a sub\-2n2^\{n\}running time can be achieved using only polynomial space\. The latter is open even for computing the chromatic number: all knownO∗​\(2n\)O^\{\*\}\(2^\{n\}\)\-time algorithms use exponential space\[[WGJ\+26](https://arxiv.org/html/2607.25973#bib.bib60),[GL23](https://arxiv.org/html/2607.25973#bib.bib59)\]\.

## References

- \[AW14\]A\. Abboud and V\. V\. Williams\(2014\)Popular conjectures imply strong lower bounds for dynamic problems\.InProceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science,pp\. 434–443\.External Links:[Document](https://dx.doi.org/10.1109/FOCS.2014.53)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[APT79\]B\. Aspvall, M\. F\. Plass, and R\. E\. Tarjan\(1979\)A linear\-time algorithm for testing the truth of certain quantified boolean formulas\.Information Processing Letters8\(3\),pp\. 121–123\.External Links:[Document](https://dx.doi.org/10.1016/0020-0190%2879%2990002-4),[Link](https://doi.org/10.1016/0020-0190(79)90002-4)Cited by:[§5\.1](https://arxiv.org/html/2607.25973#S5.SS1.17.p1.5)\.
- \[BI15\]A\. Backurs and P\. Indyk\(2015\)Edit distance cannot be computed in strongly subquadratic time \(unless SETH is false\)\.InProceedings of the Forty\-Seventh Annual ACM Symposium on Theory of Computing,pp\. 51–58\.External Links:[Document](https://dx.doi.org/10.1145/2746539.2746612)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[BE05\]R\. Beigel and D\. Eppstein\(2005\)3\-coloring in timeO​\(1\.3289n\)O\(1\.3289^\{n\}\)\.Journal of Algorithms54\(2\),pp\. 168–204\.External Links:[Document](https://dx.doi.org/10.1016/j.jalgor.2004.06.008),[Link](https://doi.org/10.1016/j.jalgor.2004.06.008)Cited by:[Appendix A](https://arxiv.org/html/2607.25973#A1.p3.2),[§1](https://arxiv.org/html/2607.25973#S1.p5.18),[§2](https://arxiv.org/html/2607.25973#S2.p3.8),[§2](https://arxiv.org/html/2607.25973#S2.p6.15),[§3\.5](https://arxiv.org/html/2607.25973#S3.SS5.p4.8),[Corollary 4\.3](https://arxiv.org/html/2607.25973#S4.Thmtheorem3.p1.7.7)\.
- \[BCH\+25\]A\. Björklund, R\. Curticapean, T\. Husfeldt, P\. Kaski, and K\. Pratt\(2025\)Fast deterministic chromatic number under the asymptotic rank conjecture\.InProceedings of the 2025 Annual ACM–SIAM Symposium on Discrete Algorithms \(SODA\),pp\. 2804–2818\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611978322.91)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.SS0.SSS0.Px1.p2.2)\.
- \[BHK\+07\]A\. Björklund, T\. Husfeldt, P\. Kaski, and M\. Koivisto\(2007\)Fourier meets Möbius: fast subset convolution\.InProceedings of the 39th Annual ACM Symposium on Theory of Computing \(STOC 2007\),D\. S\. Johnson and U\. Feige \(Eds\.\),New York, NY, USA,pp\. 67–74\.External Links:ISBN 978\-1\-59593\-631\-8,[Document](https://dx.doi.org/10.1145/1250790.1250801),[Link](https://doi.org/10.1145/1250790.1250801)Cited by:[Appendix A](https://arxiv.org/html/2607.25973#A1.p6.1),[§2\.1](https://arxiv.org/html/2607.25973#S2.SS1.p1.1),[§2](https://arxiv.org/html/2607.25973#S2.p6.10),[§3\.4](https://arxiv.org/html/2607.25973#S3.SS4.1.p1.12),[§3\.4](https://arxiv.org/html/2607.25973#S3.SS4.p1.3),[§3\.4](https://arxiv.org/html/2607.25973#S3.SS4.p2.5)\.
- \[BHK\+10\]A\. Björklund, T\. Husfeldt, P\. Kaski, and M\. Koivisto\(2010\)Trimmed moebius inversion and graphs of bounded degree\.Theory of Computing Systems47\(3\),pp\. 637–654\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.SS0.SSS0.Px1.p1.2)\.
- \[BHK09\]A\. Björklund, T\. Husfeldt, and M\. Koivisto\(2009\)Set partitioning via inclusion–exclusion\.SIAM Journal on Computing39\(2\),pp\. 546–563\.External Links:[Document](https://dx.doi.org/10.1137/070683933),[Link](https://doi.org/10.1137/070683933)Cited by:[Appendix A](https://arxiv.org/html/2607.25973#A1.p3.2),[§1](https://arxiv.org/html/2607.25973#S1.p4.4),[§1](https://arxiv.org/html/2607.25973#S1.p7.15),[§2](https://arxiv.org/html/2607.25973#S2.p6.10),[§3\.1](https://arxiv.org/html/2607.25973#S3.SS1.p5.11),[§3\.4](https://arxiv.org/html/2607.25973#S3.SS4.p1.3)\.
- \[BK24\]A\. Björklund and P\. Kaski\(2024\)The asymptotic rank conjecture and the set cover conjecture are not both true\.InProceedings of the 56th Annual ACM Symposium on Theory of Computing \(STOC\),pp\. 859–870\.External Links:[Document](https://dx.doi.org/10.1145/3618260.3649656)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.SS0.SSS0.Px1.p2.2)\.
- \[BRI14\]K\. Bringmann\(2014\)Why walking the dog takes time: fréchet distance has no strongly subquadratic algorithms unless SETH fails\.InProceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science,pp\. 661–670\.External Links:[Document](https://dx.doi.org/10.1109/FOCS.2014.76)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[BYS04\]J\. M\. Byskov\(2004\)Enumerating maximal independent sets with applications to graph colouring\.Operations Research Letters32\(6\),pp\. 547–556\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p4.4)\.
- \[CDL\+16\]M\. Cygan, H\. Dell, D\. Lokshtanov, D\. Marx, J\. Nederlof, Y\. Okamoto, R\. Paturi, S\. Saurabh, and M\. Wahlström\(2016\)On problems as hard as CNF\-SAT\.ACM Transactions on Algorithms12\(3\),pp\. 41:1–41:24\.External Links:[Document](https://dx.doi.org/10.1145/2925416)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[EPP01\]D\. Eppstein\(2001\)Small maximal independent sets and faster exact graph coloring\.InWorkshop on Algorithms and Data Structures,pp\. 462–470\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p4.4)\.
- \[FK10\]F\.V\. Fomin and D\. Kratsch\(2010\)Exact exponential algorithms\.Texts in Theoretical Computer Science\. An EATCS Series,Springer Berlin Heidelberg\.External Links:ISBN 9783642165337Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[FGS07\]F\. V\. Fomin, S\. Gaspers, and S\. Saurabh\(2007\)Improved exact algorithms for counting 3\-and 4\-colorings\.InInternational Computing and Combinatorics Conference,pp\. 65–74\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p5.18)\.
- \[FK13\]F\. V\. Fomin and P\. Kaski\(2013\)Exact exponential algorithms\.Communications of the ACM56\(3\),pp\. 80–88\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[GL23\]S\. Gaspers and E\. J\. Lee\(2023\)Faster graph coloring in polynomial space\.Algorithmica85,pp\. 584–609\.External Links:[Document](https://dx.doi.org/10.1007/s00453-022-01034-7)Cited by:[§7](https://arxiv.org/html/2607.25973#S7.p5.2)\.
- \[GKM16\]A\. Golovnev, A\. S\. Kulikov, and I\. Mihajlin\(2016\)Families with infants: speeding up algorithms for np\-hard problems using fft\.ACM Transactions on Algorithms \(TALG\)12\(3\),pp\. 1–17\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.SS0.SSS0.Px1.p1.2)\.
- \[HKZ\+19\]T\. D\. Hansen, H\. Kaplan, O\. Zamir, and U\. Zwick\(2019\)Faster k\-sat algorithms using biased\-ppsz\.InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,pp\. 578–589\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[HER14a\]T\. Hertli\(2014\)3\-SAT faster and simpler \- unique\-SAT bounds for PPSZ hold in general\.SIAM J\. Comput\.43\(2\),pp\. 718–729\.Note:Announced at FOCS’11\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[HER14b\]T\. Hertli\(2014\)Breaking the PPSZ barrier for unique 3\-SAT\.InProc\. of 41st ICALP I,pp\. 600–611\.External Links:[Link](https://doi.org/10.1007/978-3-662-43948-7%5C_50),[Document](https://dx.doi.org/10.1007/978-3-662-43948-7%5F50)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[IPZ01\]R\. Impagliazzo, R\. Paturi, and F\. Zane\(2001\)Which problems have strongly exponential complexity?\.Journal of Computer and System Sciences63\(4\),pp\. 512–530\.External Links:[Document](https://dx.doi.org/10.1006/jcss.2001.1774)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1),[§1](https://arxiv.org/html/2607.25973#S1.p3.7)\.
- \[IP01\]R\. Impagliazzo and R\. Paturi\(2001\)On the complexity ofkk\-SAT\.J\. Comput\. Syst\. Sci\.62\(2\),pp\. 367–375\.External Links:[Link](https://doi.org/10.1006/jcss.2000.1727),[Document](https://dx.doi.org/10.1006/jcss.2000.1727)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1),[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[KAR72\]R\. M\. Karp\(1972\)Reducibility among combinatorial problems\.InComplexity of computer computations,pp\. 85–103\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p1.5)\.
- \[KUM92\]V\. Kumar\(1992\)Algorithms for constraint\-satisfaction problems: a survey\.AI magazine13\(1\),pp\. 32–32\.Cited by:[§3\.1](https://arxiv.org/html/2607.25973#S3.SS1.p3.17)\.
- \[LAW76\]E\. L\. Lawler\(1976\)A note on the complexity of the chromatic number problem\.\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p4.4)\.
- \[LOV73\]L\. Lovász\(1973\)Coverings and colorings of hypergraphs\.InProc\. 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing,pp\. 3–12\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p1.5)\.
- \[MEI23\]L\. Meijer\(2023\)3\-coloring in time o \(1\.3217ˆn\)\.arXiv preprint arXiv:2302\.13644\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p5.18)\.
- \[MS85\]B\. Monien and E\. Speckenmeyer\(1985\)Solving satisfiability in less than2n2^\{n\}steps\.Discrete Applied Mathematics10\(3\),pp\. 287–295\.External Links:[Link](https://doi.org/10.1016/0166-218X(85)90050-2),[Document](https://dx.doi.org/10.1016/0166-218X%2885%2990050-2)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[MM65\]J\. W\. Moon and L\. Moser\(1965\)On cliques in graphs\.Israel journal of Mathematics3\(1\),pp\. 23–28\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p4.4)\.
- \[PPS\+05\]R\. Paturi, P\. Pudlák, M\. E\. Saks, and F\. Zane\(2005\)An improved exponential\-time algorithm forkk\-SAT\.J\. ACM52\(3\),pp\. 337–364\.Note:Announced at FOCS’98\.External Links:[Link](http://doi.acm.org/10.1145/1066100.1066101),[Document](https://dx.doi.org/10.1145/1066100.1066101)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[PPZ99\]R\. Paturi, P\. Pudlák, and F\. Zane\(1999\)Satisfiability coding lemma\.Chicago J\. Theor\. Comput\. Sci\.\.External Links:[Link](http://cjtcs.cs.uchicago.edu/articles/1999/11/contents.html)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[PU59\]M\. C\. Paull and S\. H\. Unger\(1959\)Minimizing the number of states in incompletely specified sequential switching functions\.IRE Transactions on Electronic Computers\(3\),pp\. 356–367\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p4.4)\.
- \[PRA24\]K\. Pratt\(2024\)A stronger connection between the asymptotic rank conjecture and the set cover conjecture\.InProceedings of the 56th Annual ACM Symposium on Theory of Computing \(STOC\),pp\. 871–874\.External Links:[Document](https://dx.doi.org/10.1145/3618260.3649620)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.SS0.SSS0.Px1.p2.2)\.
- \[ROD96\]R\. Rodošek\(1996\)A new approach on solving 3\-satisfiability\.InArtificial Intelligence and Symbolic Mathematical Computation, International Conference AISMC\-3, Steyr, Austria, September 23\-25, 1996, Proceedings,pp\. 197–212\.External Links:[Link](https://doi.org/10.1007/3-540-61732-9%5C_59),[Document](https://dx.doi.org/10.1007/3-540-61732-9%5F59)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[SS17\]D\. Scheder and J\. P\. Steinberger\(2017\)PPSZ for generalkk\-SAT \- making Hertli’s analysis simpler and 3\-SAT faster\.In32nd Computational Complexity Conference, CCC 2017, July 6\-9, 2017, Riga, Latvia,pp\. 9:1–9:15\.External Links:[Link](https://doi.org/10.4230/LIPIcs.CCC.2017.9),[Document](https://dx.doi.org/10.4230/LIPIcs.CCC.2017.9)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[SCH93\]I\. Schiermeyer\(1993\)Deciding 3\-colourability in less thanO​\(1\.415n\)O\(1\.415^\{n\}\)steps\.InInternational Workshop on Graph\-Theoretic Concepts in Computer Science,pp\. 177–188\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p5.18)\.
- \[SCH99\]T\. Schoning\(1999\)A probabilistic algorithm for k\-SAT and constraint satisfaction problems\.In40th Annual Symposium on Foundations of Computer Science \(Cat\. No\. 99CB37039\),pp\. 410–414\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7),[§3\.1](https://arxiv.org/html/2607.25973#S3.SS1.p3.17),[§7](https://arxiv.org/html/2607.25973#S7.p2.8)\.
- \[STO73\]L\. Stockmeyer\(1973\)Planar 3\-colorability is polynomial complete\.ACM Sigact News5\(3\),pp\. 19–25\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p1.5)\.
- \[TRA08\]P\. Traxler\(2008\)The time complexity of constraint satisfaction\.InParameterized and Exact Computation: Third International Workshop, IWPEC 2008, Victoria, BC, Canada, May 14–16, 2008, Proceedings,M\. Grohe and R\. Niedermeier \(Eds\.\),Lecture Notes in Computer Science, Vol\.5018,Berlin, Heidelberg,pp\. 190–201\.External Links:[Document](https://dx.doi.org/10.1007/978-3-540-79723-4%5F18),[Link](https://doi.org/10.1007/978-3-540-79723-4_18)Cited by:[§2](https://arxiv.org/html/2607.25973#S2.p7.4),[§3\.1](https://arxiv.org/html/2607.25973#S3.SS1.p5.11),[§4\.4](https://arxiv.org/html/2607.25973#S4.SS4.1.p1.12)\.
- \[VW21\]N\. Vyas and R\. R\. Williams\(2021\)On super strong ETH\.Journal of Artificial Intelligence Research70,pp\. 473–495\.External Links:[Document](https://dx.doi.org/10.1613/JAIR.1.11859)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p3.7)\.
- \[WW18\]V\. V\. Williams and R\. R\. Williams\(2018\)Subcubic equivalences between path, matrix, and triangle problems\.Journal of the ACM65\(5\),pp\. 27:1–27:38\.External Links:[Document](https://dx.doi.org/10.1145/3186893)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[WIL18\]V\. V\. Williams\(2018\)On some fine\-grained questions in algorithms and complexity\.InProceedings of the International Congress of Mathematicians 2018,pp\. 3447–3487\.External Links:[Document](https://dx.doi.org/10.1142/9789813272880%5F0188)Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[WOE03\]G\. J\. Woeginger\(2003\)Exact algorithms for NP\-hard problems: a survey\.InCombinatorial optimization—eureka, you shrink\!,pp\. 185–207\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p2.1)\.
- \[WGJ\+24\]P\. Wu, H\. Gu, H\. Jiang, Z\. Shao, and J\. Xu\(2024\)A faster algorithm for the 4\-coloring problem\.In32nd Annual European Symposium on Algorithms \(ESA 2024\),pp\. 103–1\.Cited by:[§1](https://arxiv.org/html/2607.25973#S1.p5.18)\.
- \[WGJ\+26\]P\. Wu, H\. Gu, H\. Jiang, Z\. Shao, and J\. Xu\(2026\)A space improved algorithm for chromatic number\.Theoretical Computer Science1059,pp\. 115584\.External Links:[Document](https://dx.doi.org/10.1016/j.tcs.2025.115584)Cited by:[§7](https://arxiv.org/html/2607.25973#S7.p5.2)\.
- \[ZAM21\]O\. Zamir\(2021\)Breaking the2n2^\{n\}barrier for 5\-coloring and 6\-coloring\.In48th International Colloquium on Automata, Languages, and Programming \(ICALP 2021\),N\. Bansal, E\. Merelli, and J\. Worrell \(Eds\.\),Leibniz International Proceedings in Informatics \(LIPIcs\), Vol\.198,Dagstuhl, Germany,pp\. 113:1–113:20\.External Links:[Document](https://dx.doi.org/10.4230/LIPIcs.ICALP.2021.113),[Link](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.113)Cited by:[Appendix A](https://arxiv.org/html/2607.25973#A1.p3.2),[Appendix A](https://arxiv.org/html/2607.25973#A1.p4.1),[§1](https://arxiv.org/html/2607.25973#S1.SS0.SSS0.Px1.p1.2),[§1](https://arxiv.org/html/2607.25973#S1.p5.18),[§1](https://arxiv.org/html/2607.25973#S1.p9.9),[§2\.1](https://arxiv.org/html/2607.25973#S2.SS1.p1.1),[§2](https://arxiv.org/html/2607.25973#S2.p1.4),[§2](https://arxiv.org/html/2607.25973#S2.p3.8),[§3\.2](https://arxiv.org/html/2607.25973#S3.SS2.p1.3),[§3\.5](https://arxiv.org/html/2607.25973#S3.SS5.p1.1),[§3\.5](https://arxiv.org/html/2607.25973#S3.SS5.p4.8),[Theorem 3\.5](https://arxiv.org/html/2607.25973#S3.Thmtheorem5),[Theorem 3\.6](https://arxiv.org/html/2607.25973#S3.Thmtheorem6),[§4\.1](https://arxiv.org/html/2607.25973#S4.SS1.p1.1),[§4\.2](https://arxiv.org/html/2607.25973#S4.SS2.p1.16),[§4\.2](https://arxiv.org/html/2607.25973#S4.SS2.p4.1),[§4](https://arxiv.org/html/2607.25973#S4.p1.7),[§4](https://arxiv.org/html/2607.25973#S4.p4.4),[§6\.2](https://arxiv.org/html/2607.25973#S6.SS2.SSS0.Px4.p1.3),[§6](https://arxiv.org/html/2607.25973#S6.p2.2)\.
- \[ZAM22\]O\. Zamir\(2022\)Faster algorithm for unique\(k,2\)\(k,2\)\-CSP\.In30th Annual European Symposium on Algorithms \(ESA 2022\),S\. Chechik, G\. Navarro, E\. Rotenberg, and G\. Herman \(Eds\.\),Leibniz International Proceedings in Informatics \(LIPIcs\), Vol\.244,Dagstuhl, Germany,pp\. 92:1–92:13\.External Links:[Document](https://dx.doi.org/10.4230/LIPIcs.ESA.2022.92),[Link](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.92)Cited by:[Appendix A](https://arxiv.org/html/2607.25973#A1.p3.2)\.
- \[ZAM23\]O\. Zamir\(2023\)Algorithmic applications of hypergraph and partition containers\.InProceedings of the 55th Annual ACM Symposium on Theory of Computing,pp\. 985–998\.External Links:[Document](https://dx.doi.org/10.1145/3564246.3585163),[Link](https://doi.org/10.1145/3564246.3585163)Cited by:[Appendix A](https://arxiv.org/html/2607.25973#A1.p3.2),[§1](https://arxiv.org/html/2607.25973#S1.SS0.SSS0.Px1.p1.2),[§1](https://arxiv.org/html/2607.25973#S1.p9.9),[§2\.1](https://arxiv.org/html/2607.25973#S2.SS1.p1.1),[§2](https://arxiv.org/html/2607.25973#S2.p12.4),[§3\.6](https://arxiv.org/html/2607.25973#S3.SS6.p1.1),[§3\.6](https://arxiv.org/html/2607.25973#S3.SS6.p2.6),[§3\.6](https://arxiv.org/html/2607.25973#S3.SS6.p3.1),[§4\.5](https://arxiv.org/html/2607.25973#S4.SS5.p2.4),[§5](https://arxiv.org/html/2607.25973#S5.p5.12)\.

## Appendix AAI Storytime

All main proof ideas in this work were mine; nonetheless, this project was the first time I found interacting with AI tools useful and productive\. This non\-mathematical section describes the methods I found practical, together with some cautions and broader discussion\.

I used OpenAI’s ChatGPT 5\.6 Sol model with its memory feature turned on\. The model frequently searches previous chats, including seemingly unrelated ones\. I even ‘caught’ it using constructions I had described in earlier chats without attribution: a reference to the previous chat appeared in the animated ‘thinking’ glimpse but not in the final answer\. Thus, my account of the prompts I supplied might not reveal the full context I inadvertently provided the model with\.

Approaching this project, I already had a cohesive proof strategy in mind, building upon prior works\. Still, as a sanity check and out of curiosity, I initially withheld it from the AI and revealed it only as needed\. I began by providing\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\]as the main context and\[[BHK09](https://arxiv.org/html/2607.25973#bib.bib4),[ZAM22](https://arxiv.org/html/2607.25973#bib.bib6),[ZAM23](https://arxiv.org/html/2607.25973#bib.bib8),[BE05](https://arxiv.org/html/2607.25973#bib.bib2)\]as additional reading, then asked it to generalize the attached paper by one step, from66\-coloring to77\-coloring\. After long thinking, the model came back empty\-handed\.

Next, I gave it a promising lead, similar to what I would give an early\-stage graduate student: an informal, concise but complete description of the high\-level strategy at the beginning of Section[4](https://arxiv.org/html/2607.25973#S4)\. I explained what goes wrong in the natural extension of\[[ZAM21](https://arxiv.org/html/2607.25973#bib.bib7)\], the remaining obstruction of many size\-two lists, and the desired reduction to the clean problem of list\-coloring with many such lists\. I then asked it to \(a\) verify the reduction, which I had described only informally, and \(b\) solve the resulting interpolation problem\. The first task was easy: the model repeated the proof details from the paper, generalized them by one color, and reached the same obstruction I had in mind\. The second was not: it again thought for a while and drew a blank\. Generic encouragement or additional thinking time did not help\.

I therefore supplied a more concrete direction\. Although the fully general formulation is cleaner, our application has a bounded color palette, so the*same*size\-two list must occur on a constant fraction of the variables\. I instructed it to focus on this easier case, at which point the model successfully completed the algorithmic argument\. The needed observation was clearly legible from the algorithm it provided: once all short lists contain the same two colors, it suffices to determine which induced subgraphs of the remaining vertices are colorable without those colors\.

The bad news, or another cautionary tale, is that instead of citing\[[BHK\+07](https://arxiv.org/html/2607.25973#bib.bib3)\], which I had not provided as context, and using their all\-subgraph coloring result as a black box, the model essentially reproduced \(or copied\) their entire proof with the new observation mixed into it\. Thus, while essentially correct, the algorithm was unnecessarily complicated and displayed a severe lack of attribution\. A user less familiar with the area could easily believe the AI had invented the convolution framework and unknowingly repeat published work without citation\.

Generally, the model almost felt like simulating an early\-stage graduate student\. I provided proof frameworks and received a good indication of whether the details could be filled in, or of the precise remaining obstruction\. Unlike a student, its occasional mistakes were more adversarially hidden, and its attributions unreliable\. On the other hand, what might have emerged from a weekly meeting became a rapid prompt–response cycle\. This already feels like a noticeable speed multiplier\.

An immediate downside is the apparent loss of what I once considered the best problems for training such early\-stage students\. If a publicly available machine can now turn a sufficiently strong lead into a solution, without the corresponding understanding and effort, then it may soon become unreasonable to train students on such problems\.

I also used AI models to help generate the figures in this paper\. One may look at them and ask whether these outputs are anything to be proud of\. I would refer that one to the manually drawn figures in my older papers and ask them to appreciate, at least, the relative improvement\.