Toward Vu's conjecture

Abhishek Dhawan; Abhishek Methuku; Michael C. Wigal; Peter Bradshaw

REVIEW 3 major objections 3 minor 1 cited by

Toward Vu's conjecture

T0 review · 3 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read This paper proves the first sparse-regime bound for Vu's conjecture: graphs with maximum degree Δ and codegree at most ζΔ have chromatic number at most (ζ^{1/32}+o(1))Δ.

desk verdict First credible progress on the sparse regime of Vu's conjecture, but the abstract leaves a quantifier-order issue that the proof must settle. read the letter →

arxiv 2508.16818 v2 pith:F7TL423S submitted 2025-08-22 math.CO cs.DM

Peter Bradshaw , Abhishek Dhawan , Abhishek Methuku , Michael C. Wigal This is my paper · ORCID

classification math.COcs.DM MSC 05C1505C35

keywords Vu'sconjecturechromaticnumbermaximumcodegreesparseregimelistcoloringcommonneighborhoodgraphasymptoticbounds

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

Vu's 2002 conjecture says that if a graph has maximum degree Δ and no two vertices share more than ζΔ common neighbors, then it can be colored with about ζΔ colors. The conjecture was known only when ζ is close to 1. This paper attacks the opposite end, the sparse regime ζ≪1, and proves that for every ζ between log^{-32}Δ and some small constant ζ0, the chromatic number is at most (ζ^{1/32}+o(1))Δ. This is a much weaker bound than the conjectured ζΔ, but it is the first general result in this regime. The proof actually works under a weaker 'bounded common neighborhood of any s vertices' condition, and it extends to list coloring.

What carries the argument

The key object is the s-wise common-neighborhood condition: a bound on the number of vertices adjacent to all vertices in any s-element set. Where Vu's conjecture constrains pairs (s=2), the paper's main theorem works with arbitrary fixed s and derives the pairwise case from it; this added generality is what lets the proof reach ζ≪1. The list-coloring version is obtained by the same machinery, so the argument is inherently about choosing colors for vertices whose neighborhoods are locally sparse.

What would settle it

A counterexample would be a sequence of graphs with maximum degree Δ, maximum codegree at most Δ/log^{32}Δ, and chromatic number at least c·Δ/log Δ for any fixed c>1. If such graphs exist, the theorem's bound (ζ^{1/32}+o(1))Δ with ζ=log^{-32}Δ is false.

Watch

Extended reading notes

Core claim

The central claim is that Vu's conjecture, in its natural asymptotic form, holds in the sparse regime after replacing the conjectured factor ζ by its 1/32 power. Specifically, the paper establishes the existence of ζ0>0 such that for all ζ ∈ [log^{-32}Δ, ζ0], every graph with maximum degree Δ and maximum codegree at most ζΔ satisfies χ(G) ≤ (ζ^{1/32}+o(1))Δ. The result is derived from a more general theorem that bounds the common neighborhood of every s-subset of vertices; the pairwise codegree bound is a special case (s=2). The same general theorem is proved in the list-coloring setting, meaning the bound applies to list chromatic number as well.

Load-bearing premise

The bound is asymptotic in the maximum degree Δ, and the paper does not quantify how large Δ must be for the o(1) term to be uniformly small across the whole ζ-interval.

Editorial extensions

If this is right

At the lower end of the range, ζ=log^{-32}Δ, the theorem gives χ(G) ≤ (1/log Δ + o(1))Δ, so graphs with very tiny codegree admit colorings using far fewer than Δ colors.
The list-coloring extension means the same bound holds for list chromatic number: any assignment of lists of size (ζ^{1/32}+o(1))Δ permits a proper coloring respecting the lists.
The s-wise common-neighborhood theorem covers graphs where small sets of vertices have few common neighbors even if pairwise codegrees are not uniformly bounded, broadening the class of graphs for which such a coloring bound is known.
The dense-regime result from earlier work and this sparse-regime result now bracket Vu's conjecture from both ends of ζ; the middle interval ζ0 < ζ < 1-ε remains untouched.

Reading between the lines

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

The exponent 1/32 is likely not optimal; Vu's conjecture asks for exponent 1, and the proof technique may be optimizable to yield ζ^{c}Δ for some c between 1/32 and 1. The paper does not claim optimality.
The choice of log^{-32}Δ as the lower endpoint suggests the method relies on ζ not being too small relative to Δ; extending the result to ζ as small as polynomial in 1/Δ might require new ideas, or might be false in that range.
The s-wise common-neighborhood generalization is a natural strengthening that could have applications to hypergraph colorings, where common neighborhoods correspond to intersections of edges.
Because the proof is asymptotic, a finite-Δ quantitative version (explicit bounds on how large Δ must be) would be needed to use the result in algorithmic or computational coloring contexts.

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 you should know: this is the first real movement on Vu's conjecture in the regime that actually matters, the sparse one (zeta << 1). If the proof holds, it's a genuine advance. The abstract alone can't confirm that, so the usual caveat applies, but the claim is specific and plausible rather than hand-wavy.

What's new and good: they extend beyond pairwise codegree to a bounded common neighborhood for any s vertices, and they get a list-coloring version as a byproduct. The bound (zeta^{1/32}+o(1))Delta is probably not optimal, but the point is to break the dense-regime barrier, and that is what they appear to do. The exponent 1/32 is ugly, but ugly exponents are common in first proofs of this kind. Credit is earned for tackling the sparse range at all.

The soft spot is the one the stress test flags: the theorem is stated for all zeta in [log^{-32}Delta, zeta_0], with the lower endpoint shrinking as Delta grows. For that statement to be meaningful, the o(1) term must be uniform in zeta over that whole interval. Near the lower endpoint, zeta^{1/32} is about (log Delta)^{-1}, so o(1) must be smaller than that. If the proof actually shows the bound for each fixed zeta as Delta tends to infinity, with the error depending on zeta, then the stated range, especially the log^{-32}Delta endpoint, is not covered. The abstract does not specify the quantifier order, and that is not a pedantic point; it changes what the theorem claims. I also note the abstract gives no explicit zeta_0 and no statement about how large Delta must be. These may be harmless details the full paper handles, but they are exactly the parts that need a referee's eye.

I did not see anything in the abstract that smells like circular reasoning or fitted constants. The 1/32 exponent could be an artifact of the method, but that is not a flaw on its own.

Who is this for? People working on codegree bounds, graph coloring, and Vu's conjecture. It deserves a serious referee: the problem is important, the claim is concrete, and the uniformity issue is exactly what a referee can resolve.

Recommendation: send it to peer review. If the proof delivers uniform control, this is a publishable paper at a strong journal. If not, the authors need to revise the statement to match the proof.

Referee Report

3 major / 3 minor

Summary. The paper's central claim (Abstract, main theorem) is that for every ζ in the interval [log^{-32}Δ, ζ0], every graph on maximum degree Δ and maximum codegree at most ζΔ has chromatic number at most (ζ^{1/32}+o(1))Δ. This is presented as the first progress in the sparse regime (ζ<<1) of Vu's 2002 conjecture. The result is said to follow from a more general statement involving bounded common neighborhoods of any s vertices, and to extend to list coloring. The abstract is the only part of the manuscript available for this review; no proof is provided in the material I received.

Significance. If the claimed theorem is correct, it would be a substantial advance: it gives the first nontrivial upper bound in the sparse regime of Vu's conjecture, with an explicit power ζ^{1/32}, and the more general s-wise and list-coloring versions would be of independent interest. The result is not a restatement of known bounds and appears to be genuinely new. However, because the proof is not available to the reviewer, the significance cannot be fully assessed. The paper does not appear to include machine-checked proofs, code, or a parameter-free derivation beyond the stated exponent; these would strengthen confidence.

major comments (3)

[Abstract, main theorem] The quantifier order of the o(1) term is load-bearing and not specified. The theorem states that for all ζ in [log^{-32}Δ, ζ0], χ(G) ≤ (ζ^{1/32}+o(1))Δ. Since the lower endpoint depends on Δ, at ζ=log^{-32}Δ we have ζ^{1/32}=log^{-1}Δ, so the o(1) term must be o(log^{-1}Δ) uniformly in ζ for the bound to be meaningful. If the proof establishes the bound for each fixed ζ as Δ→∞, with the o(1) depending on ζ, then the stated interval, especially its lower endpoint, is not covered. The abstract must clarify whether the o(1) is uniform over the Δ-dependent interval or whether the statement is intended as a family of fixed-ζ results.
[Abstract, general s-wise result] The paper says the theorem is derived from a more general result assuming bounded common neighborhoods of any s vertices. If that general result has an error term or leading term involving ζ^{1/s}, then for s<32 the term ζ^{1/s} = (log Δ)^{-32/s} dominates ζ^{1/32} at the lower endpoint, making the claimed bound vacuous or false. The abstract does not state the exact dependence on s or the required relation between s and the exponent 1/32. This is a concrete gap in the statement as presented.
[Abstract, asymptotic scope] The constants ζ0 and the threshold for 'sufficiently large Δ' are not specified. The interval [log^{-32}Δ, ζ0] is empty unless Δ is large enough that log^{-32}Δ ≤ ζ0; also the o(1) term is asymptotic in Δ. The abstract should state whether the result is purely asymptotic, whether the o(1) is effective, and whether any uniformity in ζ0 is intended. These details affect the validity of the claimed range, especially near the endpoints of the interval.

minor comments (3)

[Abstract, notation] The constants ζ0 and the function o(1) are not quantified. Please define the limit in which o(1) tends to zero (presumably Δ→∞) and whether the limit is uniform in ζ.
[Abstract, definitions] The term 'maximum codegree' should be defined explicitly (for example, the maximum over distinct vertices u,v of |N(u)∩N(v)|), and the graph should be stated to be simple and finite.
[Abstract, literature context] The statement 'the only direct progress so far has been obtained in the dense regime' would benefit from precise references to Hurley, de Verclos, and Kang's work, so readers can verify the novelty claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity evident from the abstract-only review

full rationale

The available material is the abstract only; no derivation chain, equations, or proof details are provided for inspection. The claimed theorem — that graphs with maximum degree Δ and maximum codegree at most ζΔ have chromatic number at most (ζ^{1/32}+o(1))Δ in the stated sparse regime — is presented as a new asymptotic result, not as a restatement of its assumptions. There is no fitted parameter renamed as a prediction, no self-citation invoked as load-bearing support, and no known result being repackaged under new coordinates. The only substantive concern identifiable from the abstract is the uniformity of the o(1) term over the Δ-dependent interval [log^{-32}Δ, ζ0]; while that is a legitimate potential correctness issue, it is not a circularity concern under the given criteria. The skeptical point about quantifier order concerns the theorem's validity or precision, not whether its conclusion is equivalent to its inputs by construction. Therefore the circularity score is 0.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

These are the constants and background assumptions we can infer from the abstract. The exponent 1/32 and the logarithmic threshold are proof choices rather than objects with independent meaning. The axioms are standard in the field but not explicitly stated.

free parameters (3)

1/32 exponent = 1/32
Chosen by the authors; any sufficiently small positive exponent might work, and 1/32 is an arbitrary proof constant not derived from a uniqueness condition.
zeta_0 = small positive constant (not specified)
The theorem asserts existence of such a constant; its value is not given in the abstract, and it is a proof-chosen threshold.
log^{-32}Delta threshold = log^{-32}Δ
A lower bound on ζ needed for the proof's probabilistic estimates. The exponent 32 is a proof choice, and the threshold is chosen to make the final bound nontrivial.

assumptions (3)

standard math Standard probabilistic tools (e.g., concentration inequalities, Lovász Local Lemma) are applicable to the graph model.
Typical for such proofs, but not stated in the abstract; the bound likely depends on such tools.
domain assumption Graphs are finite and simple.
Standard in the graph coloring context, but not explicitly stated in the abstract.
domain assumption The o(1) term is uniform in ζ over the stated interval.
The abstract does not specify how the error term depends on ζ; the proof likely requires uniformity for the theorem to hold as stated.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Toward Vu's conjecture." pith.science (2026). https://pith.science/paper/F7TL423S

@misc{pith2026250816818,
  author       = {Pith},
  title        = {Pith review of: Toward Vu's conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F7TL423S}},
  note         = {Machine review of arXiv:2508.16818}
}

abstract

In 2002, Vu conjectured that graphs of maximum degree $\Delta$ and maximum codegree at most $\zeta \Delta$ have chromatic number at most $(\zeta+o(1))\Delta$. Despite its importance, the conjecture has remained widely open. The only direct progress so far has been obtained in the ``dense regime,'' when $\zeta$ is close to $1$, by Hurley, de Verclos, and Kang. In this paper we provide the first progress in the sparse regime $\zeta \ll 1$, the case of primary interest to Vu. We show that there exists $\zeta_0 > 0$ such that for all $\zeta \in [\log^{-32}\Delta,\zeta_0]$, the following holds: if $G$ is a graph with maximum degree $\Delta$ and maximum codegree at most $\zeta \Delta$, then $\chi(G) \leq (\zeta^{1/32} + o(1))\Delta$. We derive this from a more general result that assumes only that the common neighborhood of any $s$ vertices is bounded rather than the codegrees of pairs of vertices. Our more general result also extends to the list coloring setting, which is of independent interest.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Sharp bounds for the fractional chromatic number of high-girth $d$-degenerate graphs
math.CO 2026-07 conditional novelty 7.0 of 10

For d-degenerate C4-free graphs, the fractional chromatic number is at most (1+o(1))d/log d, and for every fixed girth at least 4 there are d-degenerate graphs with fractional chromatic number at least (1−o(1))d/log d.

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.