Breaking the $2^n$ barrier for graph $k$-coloring

Kevin Pratt

Breaking the $2^n$ barrier for graph $k$-coloring

T0 review · 0 major / 5 minor · reviewed 2026-07-30 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every fixed number of colors k, graph k-coloring can be decided in time O((2-ε_k)^n) by a one-sided randomized algorithm.

desk verdict Clean qualitative win: fixed-k coloring finally beats 2^n for every k, with a readable case-split proof and independent concurrent confirmation. read the letter →

arxiv 2607.27159 v1 pith:DKVRJLAW submitted 2026-07-29 cs.DS

Kevin Pratt This is my paper · ORCID

classification cs.DS MSC 68Q2505C1568R10

keywords graphcoloringexactalgorithmsexponentialtimesubsetconvolutionlisttrimmedMöbiusinversionprofile

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Graph k-coloring is a classic NP-complete problem. The long-standing general algorithm of Björklund, Husfeldt and Koivisto runs in O*(2^n) time for any k. Exponential improvements below 2^n were previously known only for k ≤ 6 and for graphs with special structure. This paper shows that the 2^n barrier can be broken for every fixed k: there is a positive ε_k (depending only on k) and a randomized algorithm with one-sided error that decides k-colorability in O((2-ε_k)^n) time. The result places coloring in the same qualitative regime as k-SAT and other parameterized CSPs, where fixing the parameter already yields a strict exponential improvement over the unbounded case. A concurrent independent proof of the same statement exists; the two approaches differ in technique.

What carries the argument

A list-coloring primitive (Theorem 4.1) that, after O*(2^{H(1/2-η)n}) preprocessing via trimmed subset convolution, answers queries “does there exist a profile-p coloring in which a given set A receives colors from a palette R?” in time O*(2^{n-|A|}) whenever R is η-good or |R| ≤ 2. The main algorithm routes every witness coloring into one of three cases (many low-degree vertices, many vertices whose neighborhoods are almost η-good, or many vertices that see a heavy non-good palette) and reduces each case to this primitive or to an existing bounded-degree list-coloring routine.

What would settle it

Implement the full algorithm for a concrete small k (say k=7) with the stated parameter settings, run it on a family of n-vertex graphs known to be 7-colorable, and check whether the measured running time is consistently o(2^n) while the acceptance probability on yes-instances stays bounded away from zero.

Watch

Extended reading notes

Core claim

For every fixed integer k ❥ 3 there exists ε_k > 0 such that Graph k-coloring admits a randomized one-sided-error algorithm running in time O((2-ε_k)^n). The algorithm always rejects non-k-colorable graphs and accepts k-colorable graphs with probability at least 2/3. The same statement holds when the target color-class sizes (the profile) are fixed in advance.

Load-bearing premise

The argument treats as a black box an earlier algorithm that already solves k-list-coloring exponentially faster than 2^n on graphs that contain a constant fraction of bounded-degree vertices; if that subroutine fails for the concrete degree bounds used here, the claimed savings disappear in two of the three cases.

Editorial extensions

If this is right

For every fixed k the exponential base of exact k-coloring is strictly smaller than 2.
The same base improvement holds when color-class sizes are prescribed in advance.
Only graphs that are simultaneously dense, highly irregular, and free of large almost-good palettes remain candidates for a true 2^n lower bound under standard algorithmic techniques.
The trimmed-convolution / list-restriction template becomes a reusable primitive for other partition problems indexed by a fixed number of parts.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same case-split-plus-restriction idea may transfer to other fixed-arity CSPs whose natural 2^n algorithms rely on subset convolution or inclusion-exclusion.
Because ε_k tends to zero with k, the result does not yet yield a uniform (2-ε)^n algorithm for chromatic number; closing that gap is a natural next target.
Quantitative optimization of the many parameters (T, η, λ, d, …) could produce the first explicit numerical bases below 2 for k=7,8,….

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The one thing to know: Pratt closes the long-open gap that fixed-k graph coloring is in randomized O((2−ε_k)^n) for every k, not just k≤6 or structured graphs. That matches the shape we already have for k-SAT. Concurrent Zamir work gets the same theorem another way, so uniqueness is gone, but the result is real.

What is new is the case split on witness colorings. After peeling off the many-low-degree case with Zamir’s (α,Δ) list-coloring black box, the remaining high-degree vertices are partitioned by the palettes they “see” at least T times. Either most mass sits on η-good (light) palettes, handled by a branching routine that grows restricted sets W_R and falls back to list coloring or the trimmed-convolution primitive, or some heavy palette U_R0 is large; then random sampling of a small S plus an averaging lemma produces a usable list restriction on a linear-size set A, and Theorem 4.1 finishes in 2^{n−|A|} time. The parameters (η=1/(6(k−1)), T, ζ, λ, d) are chosen by hand so every base is strictly below 2. The write-up is constructive and the citations are standard (BHK09, BHKK08, Zamir 2021/23).

Soft spots are ordinary for this genre, not load-bearing. The proof is long and parameter-heavy; a constant-level slip is possible though none jumped out on a careful read. Everything rests on Zamir’s structured list-coloring for constant α and Δ=d(k), which is exactly the regime that paper claims. ε_k is existential and tiny. AI assistance is disclosed for repairing one base case of the branching lemma; the author says he verified everything. None of that sinks the argument.

This is for people who care about exact exponential algorithms and fine-grained CSP runtimes. A serious referee should see it. I would cite it when the 2^n barrier for coloring comes up, and I would bring the high-level case split to reading group even if we skip the constant-chasing.

Referee Report

0 major / 5 minor

Summary. The paper proves that for every fixed k ≥ 3 there exists ε_k > 0 such that Graph k-Coloring on n-vertex graphs can be solved by a randomized one-sided-error algorithm in time O((2-ε_k)^n). The algorithm works with a fixed color-class profile p and combines three regimes: (i) many low-degree vertices, handled by Zamir’s (α,Δ)-bounded list-coloring primitive; (ii) many vertices whose witness neighborhoods are concentrated on η-good palettes, handled by a branching procedure that feeds restricted list instances into a trimmed-subset-convolution oracle (Lemma 4.1); (iii) many vertices seeing a heavy palette, handled by random sampling of a small set S, brute-force coloring of S, and an averaging argument (Lemma 4.3) that produces a usable list constraint for the same oracle. Parameters (η, T, d, λ, σ, ζ, …) are chosen as explicit functions of k so that every exponential base is strictly less than 2. The result removes the 2^n barrier of Björklund–Husfeldt–Koivisto for all k, matching an independent concurrent proof of Zamir.

Significance. The 2^n poly(n) bound for k-coloring had stood since 2009; exponential improvements were previously known only for k ≤ 6 and for structured degree regimes. Establishing a uniform (2-ε_k)^n algorithm for every fixed k is a clean and long-sought advance in exact exponential algorithms. The proof is fully constructive, re-uses standard black-box primitives (trimmed Möbius inversion and Zamir’s bounded-degree list coloring) in a transparent case analysis, and supplies explicit (if tower-like) parameter settings that make the exponential savings rigorous. Concurrent independent confirmation by Zamir further supports correctness without diminishing the contribution of the distinct technical route taken here.

minor comments (5)

[Theorem 4.4 / Parameters] The parameter cascade in the proof of Theorem 4.4 (especially the concrete lower bound on T and the definition of d via Lemma 4.2) is correct but extremely dense. A short “parameter summary” table or a one-paragraph roadmap listing the inequalities that each constant is required to satisfy would make verification substantially easier.
[Lemma 4.1] In Lemma 4.1 the |R|=2 case sketches a bipartite-component DP in a footnote. Expanding the DP to a short inline paragraph (or citing a standard reference for exact 2-coloring with prescribed part sizes) would remove any ambiguity about polynomial-time solvability of that subproblem.
[Section 4] Several numerical thresholds (15/16, 99/100, 2^{-k-5}, 6k, …) appear without a single place that records why each constant is safe. Collecting them once, with the elementary inequalities they rely on, would help the reader track the probability and mass calculations in the case analysis.
[Throughout] Minor typesetting: accented characters and math operators are occasionally broken (e.g., “na ¨ ıvely”, “Bj¨ orklund”). A pass through the LaTeX source would clean these up.
[Theorem 4.4] The pseudocode block inside Theorem 4.4 mixes algorithmic steps with analysis remarks. Separating a clean algorithm listing from the surrounding correctness argument would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained algorithmic existence proof with hand-chosen parameters and external black-box primitives

full rationale

The paper is a pure exponential-time algorithms result. Theorem 1.2 / Theorem 4.4 is established by an exhaustive case split on a fixed witness coloring (many low-degree vertices; many vertices in η-good U_R; a large U_R0 with p(R0)>1/2−η), each reduced to either Zamir’s external (α,Δ)-bounded list-coloring primitive, trimmed subset convolution, or a new branching/sampling argument whose exponential bases are driven strictly below 2 by explicit parameter choices (η=1/(6(k−1)), T, d, λ, ζ, ε=1/100). Those parameters are not fitted to data and do not redefine the target runtime; they are constants depending only on k chosen so the stated inequalities close. Prior citations (BHK09, BHKK08, Zam21, Zam23) are used as standard black boxes in the regimes they claim, not as self-citations that force the conclusion. There is no prediction-equals-fit loop, no uniqueness theorem imported from the author, and no renaming of a known empirical pattern. Concurrent independent work of Zamir is acknowledged but not load-bearing. Score 0 is the correct honest finding.

Assumptions & free parameters 6 free parameters · 6 assumptions · 2 invented entities

The result is a composition of standard exact-algorithm primitives (subset convolution, trimmed Möbius inversion, list-coloring on bounded-degree-heavy graphs) with new case analysis and sampling. Free parameters are design constants chosen so exponential rates drop below 1; axioms are standard math plus cited algorithmic theorems treated as black boxes. No physical or empirical entities are introduced.

free parameters (6)

ε (low-degree fraction threshold) = 1/100
Set to 1/100 in Theorem 4.4 to split ‘many low-degree vertices’ from the hard case; any small positive constant would work with adjusted ε_k.
η (good-palette mass gap) = 1/(6(k-1))
Set to 1/(6(k−1)) so Lemma 4.3’s averaging produces a usable η-good or size-≤2 subpalette; chosen to close inequalities, not fitted to data.
T (neighborhood color multiplicity threshold) = ⌈2 ln(4k)·log k·2^{2k+7}·6k / (1−ζ)⌉
Chosen large enough as a function of k (explicit ceiling involving ln(4k), 2^{2k}, ζ) so sampling cost k^{σn} is paid for by the 2^{n−|A|} savings.
λ (branching mass cutoff in Lemma 4.2) = function of k,c,μ
Upper-bounded by min(2^{-k/8}, expression in μ,d,c) so both leaf-type runtimes are (2−δ)^n.
d (degree threshold) = function of k
max{T(k−1)+1, d(k,c)} with d(k,c)=2^{k+4}(c+1)(k+c+4) large enough for branching-factor entropy to beat λ.
success-probability constants (15/16, 99/100, 2^{-k-5}, 6k in |A|) = 15/16, 1/100, etc.
Hand-chosen fractions that make the dichotomy and Chernoff/averaging bounds give constant success probability; any sufficiently separated constants work.

assumptions (6)

domain assumption Trimmed subset convolution: families of sets of size ≤a,≤b can be convolved in O*((n choose ≤a+b)) time (Theorem 3.1 / BHKK08).
Black-box primitive used for all η-good palette precomputation and restricted convolutions in Lemma 4.1.
domain assumption For every fixed k,α,Δ there is μ_{α,Δ,k}>0 such that k-list-coloring on (α,Δ)-bounded n-vertex graphs is in O((2−μ)^n) (Theorem 3.2 / Zamir 2021).
Used for the many-low-degree branch and Base case 2 of Lemma 4.2; correctness of ε_k depends on μ>0.
domain assumption Classical O*(2^n) k-coloring via fast subset convolution / inclusion-exclusion (BHK09).
Baseline being improved; also underlies the algebraic view of colorability as partitioning into independent sets.
standard math Standard probabilistic bounds: (1−ln(4k)/T)^T < 1/(4k); binary entropy H(1/2−η)<1 for η>0; binomial coefficient estimates ∑_{i≤c}(d choose i)<(ed/c)^c.
Used throughout sampling analysis (Theorem 4.4) and branching runtime (Lemma 4.2).
standard math Enumerating all profiles (n+k−1 choose k−1) is 2^{o(n)} for fixed k, so it suffices to solve fixed-profile coloring.
Stated in §2; reduces the decision problem to Theorem 4.4.
standard math One-sided-error Monte Carlo composition: algorithms that never accept no-instances and accept yes-instances with constant probability may be repeated O(1) times to reach success probability 2/3.
Used to lift Theorem 4.4 to Theorem 1.2.

invented entities (2)

η-good palette
purpose: Identify color subsets R with p(R)≤1/2−η so R-realizable sets can be built in 2^{H(1/2−η)n}≪2^n time via trimmed convolution.
Definitional device internal to the algorithm; not an external physical entity. Falsifiable only insofar as the runtime claims are checkable.
U_R / Σ_T(v) witness neighborhood types
purpose: Partition high-degree vertices by which colors they see ≥T times in a hidden coloring, enabling the good-vs-heavy dichotomy.
Analysis-only sets unknown to the algorithm; standard witness-partition technique.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Breaking the $2^n$ barrier for graph $k$-coloring." pith.science (2026). https://pith.science/paper/DKVRJLAW

@misc{pith2026260727159,
  author       = {Pith},
  title        = {Pith review of: Breaking the $2^n$ barrier for graph $k$-coloring},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DKVRJLAW}},
  note         = {Machine review of arXiv:2607.27159}
}

abstract

We show that for all $k$, there exists $\varepsilon_k > 0$ such that graph $k$-coloring can be solved by a randomized algorithm with one-sided error in time $O((2-\varepsilon_k)^n)$. Prior to this work and independent concurrent work of Zamir [arXiv, 2026], exponential improvements over the $2^n \cdot \mathrm{poly}(n)$-time algorithm of Bj\"orklund, Husfeldt, and Koivisto [SIAM Journal on Computing, 2009] were only known for $k \le 6$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 1 linked inside Pith

[1]

444--452

Richard Beigel and David Eppstein, 3-coloring in time O (1.3446^n) : a no- MIS algorithm , Proceedings of IEEE 36th Annual Foundations of Computer Science, IEEE, 1995, pp. 444--452

1995
[2]

2, 168--204

, 3-coloring in time O (1.3289^n) , Journal of Algorithms 54 (2005), no. 2, 168--204

2005
[3]

2, 546--563

Andreas Bj \"o rklund, Thore Husfeldt, and Mikko Koivisto, Set partitioning via inclusion-exclusion, SIAM Journal on Computing 39 (2009), no. 2, 546--563

2009
[4]

Andreas Bj \"o rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto, Trimmed moebius inversion and graphs of bounded degree, 25th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2008

2008
[5]

6, 547--556

Jesper Makholm Byskov, Enumerating maximal independent sets with applications to graph colouring, Operations Research Letters 32 (2004), no. 6, 547--556

2004
[6]

2, 131--140

David Eppstein, Small maximal independent sets and faster exact graph coloring, Journal of Graph Algorithms and Applications 7 (2003), no. 2, 131--140

2003
[7]

Fedor V Fomin, Serge Gaspers, and Saket Saurabh, Improved exact algorithms for counting 3-and 4-colorings, International Computing and Combinatorics Conference, Springer, 2007, pp. 65--74

2007
[8]

29, wh freeman New York, 2002

Michael R Garey and David S Johnson, Computers and intractability, vol. 29, wh freeman New York, 2002

2002

Show all 18 references

[9]

3, 1--17

Alexander Golovnev, Alexander S Kulikov, and Ivan Mihajlin, Families with infants: Speeding up algorithms for np-hard problems using fft, ACM Transactions on Algorithms (TALG) 12 (2016), no. 3, 1--17

2016
[10]

219--241

Richard M Karp, Reducibility among combinatorial problems, 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art, Springer, 2009, pp. 219--241

1958
[11]

3, 66--67

EL Lawler, A note on the complexity of the chromatic number problem, Information Processing Letters 5 (1976), no. 3, 66--67

1976
[12]

3, 337--364

Ramamohan Paturi, Pavel Pudl \'a k, Michael E Saks, and Francis Zane, An improved exponential-time algorithm for k -sat, Journal of the ACM (JACM) 52 (2005), no. 3, 337--364

2005
[13]

177--188

Ingo Schiermeyer, Deciding 3-colourability in less than O (1.415^n) steps , International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, 1993, pp. 177--188

1993
[14]

T Schoning, A probabilistic algorithm for k -sat and constraint satisfaction problems, 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), IEEE, 1999, pp. 410--414

1999
[15]

Pu Wu, Huanyu Gu, Huiqin Jiang, Zehui Shao, and Jin Xu, A faster algorithm for the 4-coloring problem, 32nd Annual European Symposium on Algorithms (ESA 2024), Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2024, pp. 103--1

2024
[16]

Or Zamir, Breaking the 2^n barrier for 5-coloring and 6-coloring, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2021

2021
[17]

985--998

, Algorithmic applications of hypergraph and partition containers, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, pp. 985--998

2023
[18]

Or Zamir, k -Coloring Is Faster Than Computing the Chromatic Number , 2026, arXiv:2607.25973

2026 arXiv

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.

[1] [1]

444--452

Richard Beigel and David Eppstein, 3-coloring in time O (1.3446^n) : a no- MIS algorithm , Proceedings of IEEE 36th Annual Foundations of Computer Science, IEEE, 1995, pp. 444--452

1995

[2] [2]

2, 168--204

, 3-coloring in time O (1.3289^n) , Journal of Algorithms 54 (2005), no. 2, 168--204

2005

[3] [3]

2, 546--563

Andreas Bj \"o rklund, Thore Husfeldt, and Mikko Koivisto, Set partitioning via inclusion-exclusion, SIAM Journal on Computing 39 (2009), no. 2, 546--563

2009

[4] [4]

Andreas Bj \"o rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto, Trimmed moebius inversion and graphs of bounded degree, 25th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2008

2008

[5] [5]

6, 547--556

Jesper Makholm Byskov, Enumerating maximal independent sets with applications to graph colouring, Operations Research Letters 32 (2004), no. 6, 547--556

2004

[6] [6]

2, 131--140

David Eppstein, Small maximal independent sets and faster exact graph coloring, Journal of Graph Algorithms and Applications 7 (2003), no. 2, 131--140

2003

[7] [7]

Fedor V Fomin, Serge Gaspers, and Saket Saurabh, Improved exact algorithms for counting 3-and 4-colorings, International Computing and Combinatorics Conference, Springer, 2007, pp. 65--74

2007

[8] [8]

29, wh freeman New York, 2002

Michael R Garey and David S Johnson, Computers and intractability, vol. 29, wh freeman New York, 2002

2002