PaperlayerView exact revision on arXiv

Source-linked AI summary

An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs

Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda

arXiv:2610.35859v1cs.DS

TL;DR

Efficiently coloring 3-colorable graphs with few colors is a central approximation challenge. The paper develops independent-set algorithms from vector-coloring SDP solutions, combining them with a dense-progress framework and strengthening the SDP approach for 3-colorable graphs. It achieves O(n^0.1537) colors, improving on the previous O(n^0.1954) bound.

  • Problem

    Graph coloring is hard to approximate within n^(1−ε), motivating algorithms that use few colors when a graph is known to be 3-colorable.

    Source: §1.1 · p. 3

  • Method

    The paper finds large independent sets using vector-coloring SDP, Gaussian local-maximum selection, and band rounding with additional constraints for 3-colorable graphs.

    Source: §2.2 · p. 11, §6 · p. 53

  • Results

    O(n^0.1537) colors improve on the previous O(n^0.1954) bound, while the earlier framework yields O(n^1/6+o(1)) colors.

    Source: §6 · p. 53

  • Takeaways & Limitations

    The stronger guarantee uses additional SDP constraints valid specifically for 3-colorable graphs.

    Source: §2.2 · p. 11

    The improved lifting lemma cannot be applied without band rounding and Equation (2).

    Source: §2.2 · p. 11

Abstract

from arXiv · show

We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $O(n^{0.1954})$ colors by Bansal, Huang, and Lee (SODA '27). To achieve this result, we introduce a new algorithmic framework for finding a large independent set from a solution to the vector coloring SDP. Combined with the (combinatorial) dense-progress algorithm of Kawarabayashi, Thorup, and Yoneda (STOC '24), this framework yields an $n^{1/6 + o(1)}$-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve $O(n^{0.1537})$ colors.

1 Introduction

The introduction frames efficient coloring of 3-colorable graphs as a focused response to graph coloring’s hardness. It traces progress through combinatorial and SDP approaches, then presents improved guarantees for both ordinary and vector-colorable graphs.

1.1 Approximation Algorithms

  • Graph coloring is NP-hard to approximate within n^(1−ε), motivating polynomial-time algorithms that use few colors on graphs already known to be k-colorable.The 3-colorable case is highlighted as the smallest nontrivial case, with improvements there typically yielding better algorithms for larger k.Source: §1.1 · p. 3

1.2 Polynomial-Time Coloring of 3-Colorable Graphs

  • Wigderson’s O(√n)-coloring algorithm combines neighborhood-based independent sets with greedy coloring, while later work developed separate large-degree combinatorial and small-degree SDP approaches.A threshold separates the degree cases; progress on either side can improve the overall coloring algorithm.Source: §1.2 · pp. 3–5

1.3 Our Results

  • O(n^0.1537) colors suffice for every 3-colorable n-vertex graph with high probability, improving on the paper’s earlier O(n^1/6+o(1)) guarantee.The stronger result combines a larger-independent-set guarantee for 3-colorable graphs with [KTY24]’s framework.Source: §1.3 · p. 6

1.4 New Bounds on Vector 𝑘-Colorable Graphs

  • Recursive rounding gives O(n^0.1836) colors for vector 3-colorable graphs.The vector-coloring bounds are compared with the empirical lower bound of.Source: §1.4 · pp. 7–8
  • The stronger O(n^0.1537) guarantee exploits actual 3-colorability, including additional SDP constraints unavailable for general vector 3-colorable graphs.The paper notes that this bound is below the Ω(n^0.1578) lower bound for vector 3-colorable graphs.Source: §1.4 · pp. 7–8

1.5 Organization

  • The paper’s approach proceeds from an overview and vector-coloring preliminaries to independent-set algorithms, stronger SDP constraints, implementation details, and computational verification.Section 4 gives the O(n^1/6+ε)-coloring result; Section 5 develops the stronger O(n^0.1537) guarantee.Source: §1.5 · p. 8

2 Overview of Proof

The overview presents Gaussian local-maximum selection with nested cores and lifted Gaussian covers as a framework for finding large independent sets. For the stronger coloring algorithm, it adds band rounding and an improved lifting argument based on a stronger tail bound.

2.1 The 𝑛1/6+𝑜(1)-Coloring Algorithm (Section 4)

  • Gaussian local-maximum selection chooses vertices whose Gaussian projections exceed their neighbors’ projections, producing an independent set that is often of size n^5/6−o(1).A single attempt does not guarantee that size for every graph, so the algorithm samples across nested cores and removes frequently selected vertices.Source: §2.1 · p. 9
  • The analysis builds Gaussian covers with increasing thresholds, then lifts them toward shallower cores while losing only a negligible amount of probability.The lifting argument uses Ehrhard’s inequality to handle the inherited and transverse Gaussian contributions; it also extends to ordinary vector k-coloring for use in band rounding.Source: §2.1 · pp. 10–11

2.2 The 𝑂(𝑛0.1537)-Coloring Algorithm (Section 5)

  • Band rounding partitions correlations with a root into narrow intervals and seeks a large independent set in each band, using generalized vector-coloring and additional constraints for 3-colorable graphs.The analysis combines a stronger tail bound with an improved lifting lemma to show that the algorithm almost never fails for target independent-set size n^1−α, where α is approximately 0.1536995.Source: §2.2 · pp. 11–12

3 Preliminaries

This section sets graph and Gaussian conventions, defines vector-coloring relaxations, and develops geometric identities and Gaussian bounds.

3 Preliminaries

  • Neighborhoods, induced subgraphs, maximum degree, and a tie-breaking order for Gaussian projections are fixed as graph notation.The section also denotes the independent set selected by the procedure as I_F(g).Source: §3 · p. 13

3.1 Vector Coloring and SDP Relaxation

  • An ordinary vector k-coloring changes the strict edge equality to ≤; the smallest real k≥2 admitting one is the vector chromatic number.The k-coloring problem is relaxed to an SDP, whose computed strict-vector constraints allow additive error ε_SDP = e^-3n.Source: §3.1 · pp. 13–14

3.2 Vector Identities

  • For an edge xy, the edge residual v_xy is a unit vector orthogonal to v_x; strict vector 3-colorings have edge inner product -1/2.The text also gives the corresponding residual relation for a 3-coloring.Source: §3.2 · p. 14
  • With a fixed root r, the section expresses each vertex vector using its projection ρ_x onto v_r and its component orthogonal to v_r.For a neighbor y of x, the edge residual is decomposed into a component along the root-relative direction and an orthogonal remainder.Source: §3.2 · p. 14

3.3 Gaussian Notation and Bounds

  • Gaussian notation defines the standard vector g, probability and expectation over g, and the Gaussian measure γ(K); the Gaussian tail ratio e^(u^2/2)Φ(u) decreases for u≥0.The text also states a normal-tail interval bound, but its displayed inequality is not needed here.Source: §3.3 · p. 15
  • The two-block Gaussian Hölder inequality bounds an expectation of a product by the product of powered marginal expectations when P−T is positive semidefinite.The condition uses the covariance matrix T and P = diag(p1T11, p2T22).Source: §3.3 · p. 16
  • For two Gaussian projection events on subspaces with bounded cross-inner-products, the corollary bounds their joint probability by a product of marginal probabilities with exponents 1/p1 and 1/p2.It applies when (p1−1)(p2−1)≥1/4 and the cross-inner-products are bounded by half the product of vector norms.Source: §3.3 · p. 16

4 Finding a Large Independent Set from Vector 3-Coloring

This section develops methods for finding large independent sets from vector 3-colorings, using Gaussian local maxima, nested cores and covers, Ehrhard extrapolation, and iterated lifting. It establishes independent-set size guarantees in low- and high-degree regimes and conditions for Algorithm 2 to succeed.

4.1 Algorithmic Framework and Nested Cores

  • Gaussian local-maximum selection always returns an independent set, and repeated sampling prunes vertices with high estimated selection probability to form nested cores.If no sampled set reaches the target size, vertices with empirical probability at least δ/2 are deleted at each level.Source: §4.1 · pp. 17–18

4.2.2 The Low-Degree Regime

  • With probability at least 3/4, the algorithm finds an independent set of size at least n^{1-β/3-o(1)} when the maximum degree is at most n^β for 0 < β ≤ 1/3.The proof uses local-maximum probabilities and Gaussian tail bounds; the algorithm succeeds at its first level in this regime.Source: §4.2.2 · p. 19

4.3.1 Failed Trials

  • With probability at least 3/4, estimates are accurate within δ/8 at every constructed level, so surviving vertices have local-maximum probability below δ; if a trial fails throughout, its deepest core is nonempty.Source: §4.3.1 · p. 20

4.3.2 The Initial Cover

  • A root in the deepest core whose preceding-core local-maximum probability is at most e^{-t^2/2} yields a neighbor-vector (U0t, 1 − O(te^{-t^2/4}))-cover.Source: §4.3.2 · p. 21

4.4 Lifting to the Preceding Level

  • A single lifting step carries a (Ut, q)-cover from one core to the preceding core, increasing its threshold to (U + 40w)t and reducing its covering probability by t^-18.The step assumes each covered vertex has local-maximum probability at most e^{-t^2/2}.Source: §4.4 · p. 22

4.4.1 Ehrhard Extrapolation

  • Ehrhard extrapolation helps show that the transverse Gaussian projection of at least one neighbor of a parent is sufficiently large.The argument uses Ehrhard’s inequality to bound the Gaussian measure of an extrapolated convex set.Source: §4.4.1 · p. 26
  • Ehrhard extrapolation parameters are chosen to provide both the required probability bound and the target threshold ψ.Source: §4.4.1 · p. 27

4.5 Iterated Lifting

  • After o(ℓ) lifting steps, the Gaussian cover threshold exceeds H, enabling the contradiction that establishes Algorithm 2’s success.The argument starts from a cover around a deepest-core vertex and repeatedly applies the single-step lifting lemma.Source: §4.5 · pp. 30–31
  • If every empirical estimate used to construct the cores is within δ/8 of its true probability, Algorithm 2 returns an independent set of size at least T.This conditional guarantee holds for sufficiently large n.Source: §4.5 · pp. 30–31
  • For 1/3 < β ≤ 1, a randomized polynomial-time algorithm returns an independent set of size n^((2+2β)/(2+3β)-o(1)) with probability at least 1-n^-C.The guarantee assumes a 3-colorable n-vertex graph of maximum degree at most n^β and a strict vector 3-coloring; C can be any fixed positive constant.Source: §4.5 · pp. 31–32

5 Improved Sparse Progress

SparseProgress combines strengthened vector-coloring SDP constraints with correlation-band rounding to find large independent sets in 3-colorable graphs. When rounding fails, its analysis bounds band sizes, which supports the later sharpening of the Gaussian tail estimate.

5.1 Preliminaries for SparseProgress

  • For m in {1, 2}, Θ_m(S) relaxes finding a largest induced m-colorable subgraph of G[S]; for m=1 without the last constraints, it is the Lovász theta function.The intended solution assigns orthogonal color vectors to vertices in the chosen subgraph and zero vectors otherwise.Source: §5.1 · pp. 32–33

5.2 The Algorithm SparseProgress

  • Correlation bands partition vertices by their vector inner product with a root, and BuildVector supplies each band with a witness of sufficient mass.Positive bands use Θ_1 witnesses, while negative bands use Θ_2 witnesses; the choice is motivated by the simplex representation of a proper 3-coloring.Source: §5.2 · pp. 33–34
  • The framework uses auxiliary SDP witnesses for correlation bands to extract independent sets or construct vector colorings, then bounds bands whose rounding fails.The strengthened SDP also controls correlations between Gaussian projections associated with adjacent vertices.Source: §5.2 · pp. 33–34

5.3 Guarantees of Failed Band Rounding

  • A failed band-rounding call, when its VectorColoring subroutine meets its guarantee, bounds the band size by exp((C_D(ρ)+η)t^2/2) for every ρ in the band.The rounding procedures keep vertices with large witness mass; positive and negative bands use different witnesses and rounding steps.Source: §5.2 · p. 35, §5.3 · pp. 36, 39, 40

5.4 Tail Bound on the Neighborhood Maximum

This section sharpens bounds on neighborhood maxima by propagating Gaussian projection thresholds through nested cores. The resulting tail bound supports the improved lifting argument in the next subsection.

5.4 Tail Bound on the Neighborhood Maximum

  • The induction lowers neighborhood thresholds along nested cores while controlling both global projection bounds and local neighborhood maxima.At each step, the previous local bound supplies a large-measure convex set for Ehrhard extrapolation, while the global bound controls possible transmission targets.Source: §5.4 · p. 40
  • P_g[𝒢_i] and P_g[ℒ_i] are each at most (i+2)ε_t under the stated band-size and core assumptions.The bound holds for each vertex and each induction level covered by Lemma 38.Source: §5.4 · p. 41

5.4.1 Thresholds and Parameters

  • The threshold q_A=min{q_c,f_A} combines the direct band-size estimate with the stronger profile realized inductively.The parameter choice must work for every admissible neighboring correlation; computational verification certifies existence of suitable parameters.Source: §5.4.1 · pp. 42–43

5.4.2 Gaussian Bounds

  • The Gaussian bounds handle fixed vertices using independence of parent and transverse projections, and maximizers using the added SDP constraint and Gaussian Hölder inequality.The constraint Γ_rx(X) ⪰ 0 bounds correlations between the associated residual subspaces by one half.Source: §5.4.2 · pp. 43–44

5.5 Improved Lifting to the Preceding Level

The improved lifting step uses the prepared neighborhood-maximum tail bound to maintain positive threshold drift for a larger target independent set. Iterating the lift yields a high-probability independent-set guarantee for graphs with the stated degree bound.

5.5 Improved Lifting to the Preceding Level

  • A fixed cover lifts to the preceding level with threshold increased by only 1/3000 and cover parameter decreased by t^-100, under the stated neighborhood-tail condition.The improved lifting uses the prepared tail bound on the neighborhood maximum in place of the degree-based construction.Source: §5.5 · p. 49

5.6 Improved Iterated Lifting

  • One SparseProgress trial succeeds with probability at least 1/2, and O(log n) independent trials raise the success probability to at least 1−n^-C while retaining polynomial time.The proof iterates the improved lift a constant number of times after preparing the tail bound on deeper cores.Source: §5.6 · pp. 52–53
  • For 3-colorable graphs with maximum degree at most n^β, β=0.692601, SparseProgress returns an independent set of size at least n^((1+β)/2-o(1)) with probability at least 1−n^-C.The guarantee holds for every fixed C>0 with a randomized polynomial-time algorithm.Source: §5.6 · p. 53

6 Conclusion

The paper improves the coloring bound for 3-colorable graphs to O(n^0.1537), using band rounding and additional SDP constraints. It notes remaining gaps in known hardness results, discusses recent preprints, and discloses the role of language models in proof exploration.

6 Conclusion

  • O(n^0.1537) colors improves the previous O(n^0.1954) bound of Bansal, Huang, and Lee (2026).The paper also reports an O(n^(1/6+ε))-coloring algorithm and near-tight bounds for vector k-colorable graphs.Source: §6 · p. 53
  • The conclusion says known hardness results cover only constant numbers of colors, including 5-color hardness and a claimed any-constant result [FMW26].The authors present coloring every 3-colorable graph with O(n^ε) colors for every fixed ε>0 as a conjecture.Source: §6 · p. 54

Relation to Recent Preprints

  • The authors report conducting the work independently of recent preprints claiming O(n^0.1653)-coloring algorithms [NT26; MM26; Ana26; Son26].They disclose using language models during proof exploration and presentation polishing, while taking responsibility for correctness and content.Source: Relation to Recent Preprints · p. 54, AI Usage Disclosure · p. 54

A.1 Edge Residuals

The edge-residual vectors normalize the varying neighbor correlations into a common local-maximum condition. They remain perpendicular to the vertex vector and have norm at most one, rather than necessarily being unit vectors.

A.1 Edge Residuals

  • The rescaled edge residuals preserve the common local-maximum condition even when edge correlations vary, at the cost of vectors that need not be unit length.Their norm is still at most one, so the associated Gaussian projections have variance at most one.Source: §A.1 · p. 60

A.2 Local-Maximum Probabilities

This subsection develops local-maximum probability bounds shared across degree regimes and applies them to the low-degree regime. The argument lower-bounds a vertex’s local-maximum probability using a threshold bound on its neighbor projections.

A.2 Local-Maximum Probabilities

  • The authors prove a generalization of Theorem 18 that handles the low-degree regime.Source: §A.2 · p. 61
  • The local-maximum probability estimate is used in the low-degree-regime algorithmic argument, while the stated generalization also covers the case k > 2.The supplied passages do not include the full conclusion of the generalized theorem.Source: §A.2 · p. 61
  • For a vertex of degree at most n^β, a union bound uses the edge-residual norm bound to control the chance that any neighbor projection exceeds a threshold.The proof then uses Theorem 49 to lower-bound the local-maximum probability by p*, with p* = 1/2 Φ(a/c).Source: §A.2 · pp. 60–61

A.3 The High-Degree Regime

The high-degree-regime appendix adapts the Gaussian-cover argument and parameters for its setting, then uses the resulting independent-set guarantee in the proof of the general theorem. Its parameter dependence becomes delicate near specified boundaries.

A.3 The High-Degree Regime

  • The appendix’s parameter table lists only values that differ from Table 2; the remaining parameters retain Table 2’s formulas.The caption identifies Table 4 as the parameter table for Appendix A.3.Source: Table 4 · p. 61, §A.3 · p. 61
  • Edges with λ_xy > λ provide at least the lower bound established for λ_xy = λ, so the remaining lemmas can treat the equality case.Source: §A.3 · p. 62
  • The Gaussian-cover lemmas propagate a cover to a neighboring set with a higher threshold and a small probability loss.One stated bound changes a (Ut, q)-cover to a ((U + 40w)t, q − t^-18)-cover.Source: §A.3 · pp. 66–67
  • |I| ≥ n^{1−(k−2)β/(2+kβ)−o(1)} is the independent-set size guaranteed in the high-degree regime’s stated result.The supplied proof passage gives this size as a lower bound on T and hence on |I|.Source: §A.3 · p. 67
  • The proof repeats Algorithm 2 for O(log n) independent trials and returns the largest independent set obtained, keeping the total running time polynomial.The theorem’s constants and lower-order terms depend on k and β, and degenerate as k approaches 2 or β approaches (k−2)/k from above.Source: §A.3 · p. 67

B Polynomial-Time Implementation of BuildVector and Treatment of Approximate Constraints

This appendix addresses the polynomial-time implementation of BuildVector and the treatment of approximate SDP constraints.

B Polynomial-Time Implementation of BuildVector and Treatment of Approximate Constraints

B.1 Ellipsoid Method

The section implements Theorem 34 with an ellipsoid search over a convex matrix region, using an oracle that either cuts or returns a matrix with band witnesses.

B.1 Ellipsoid Method

  • For each candidate matrix, the oracle returns either a halfspace containing K but excluding the candidate, or the matrix with the required band witnesses.The candidate need not itself lie in K, and the oracle never cuts at a point of K.Source: §B.1 · p. 68
  • A proper 3-coloring supplies a Gram matrix that is perturbed toward the identity to initialize a ball contained in K.The proof bounds perturbations to the constraints to establish containment.Source: §B.1 · pp. 68, 70, 71
  • When the oracle returns a matrix and witnesses, its Gram realization gives unit vectors satisfying Theorem 34’s vector conditions, with band guarantees checked using Θ1 and Θ2.The SDP witness is computed to within ε_SDP of its objective value in polynomial time.Source: §B.1 · pp. 69–70
  • The ellipsoid method calls the oracle O(n^4 log(n/ε_SDP)) times and returns an output satisfying Theorem 34.The oracle checks the polynomially many constraints and only the bands determined by the current matrix.Source: §B.1 · pp. 68, 71

B.2 Justification of the Exact-Constraint Assumption

The section justifies treating approximate vector-coloring and semidefinite constraints as exact in the analysis, using slack and added Gaussian noise to control their effects.

B.2 Justification of the Exact-Constraint Assumption

  • An ε_SDP-approximate vector-coloring solution perturbs vectors and weights by O(ε_SDP), inducing O(nε_SDP) projection errors with probability at least 1 − e^-n.The analysis absorbs these errors into threshold slack or the o(t^2) terms in probability exponents.Source: §B.2 · p. 72
  • Near-linear dependence means an additive error in the semidefinite constraint need not preserve the correlation bound, so the proof adds tiny independent Gaussian noise to its projections.The perturbed covariance matrix is positive semidefinite, enabling the correlation argument to apply.Source: §B.2 · p. 72
  • The noisy projection families retain the needed conditional independence and correlation bound, allowing the induction argument to transfer to the original local event.The transfer incurs an O(ne^-n) probability term.Source: §B.2 · pp. 72–73

C Computational Verification

The section verifies inequalities over parameter ranges using interval-based certificates, concluding with a complete certificate and verifier for the claims.

C Computational Verification

  • For 1.968 ≤ A ≤ A0 and ρ ≥ 0.7, q_A(ρ) = q_c(ρ), so f_A(ρ) ≥ q_c(ρ).The proof reduces this property to A = 2.15 using monotonicity of f_A in A.Source: C Computational Verification · pp. 74–75
  • For A = 2.15, interval arithmetic rigorously proves f_2.15(ρ) − q_c(ρ) ≥ 0 by checking sufficiently small intervals with positive lower bounds.The program rounds interval endpoints outward to multiples of 2^-72.Source: C Computational Verification · p. 75
  • Theorem 40’s parameter domain is divided into boxes, each verified either by showing q_A(ρ) = q_c(ρ) or by finding a common tuple satisfying conditions (i)–(iv).Positivity is established by interval arithmetic or Taylor lower bounds, including over three-dimensional boxes where needed.Source: C Computational Verification · pp. 75–77
  • The verification establishes the required tuple conditions for both cases and provides a complete certificate and verifier.If a box is too large for one tuple, recursive subdivision yields a finite certificate covering the domain.Source: C Computational Verification · p. 78

Related papers

Loading 2610.35859v1…