Triangle-free $d$-degenerate graphs have small fractional chromatic number

Anders Martinsson

REVIEW 1 major objections 3 minor 27 references

Triangle-free $d$-degenerate graphs have small fractional chromatic number

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

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

Pith's one-line read A random weight process proves that triangle-free d-degenerate graphs have fractional chromatic number at most (4+o(1))d/ln d.

desk verdict Harris's conjecture is proved by a clean change-of-measure argument, and the stress-test concern about Claim 2.6 does not survive a reading of the actual update rule. read the letter →

arxiv 2501.18238 v1 pith:EIT73TL4 submitted 2025-01-30 math.CO math.PR

Anders Martinsson This is my paper · ORCID

classification math.COmath.PR MSC 05C1505C6960G42

keywords fractionalchromaticnumberdegeneracytriangle-freegraphsrandomindependentsetmartingalelocaltriangleboundinducedbipartitesubgraphShearer

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

Fractional chromatic number relaxes ordinary coloring: it is the smallest real $k$ for which independent sets can be weighted so that every vertex is covered with total weight at least $1/k$. For $d$-degenerate triangle-free graphs, only the trivial $O(d)$ upper bound was known despite a well-known conjecture that $O(d/\ln d)$ should hold. This paper proves that conjecture, showing $\chi_f(G) \le (4+o(1))\, d/\ln d$ for every triangle-free $d$-degenerate graph. A direct consequence is the conjecture that every triangle-free graph of minimum degree $d$ has an induced bipartite subgraph of minimum degree $\Omega(\ln d)$. The proof constructs a random independent set with uniform vertex-inclusion probability about $(1/4)\ln d / d$, which is exactly what a fractional coloring needs.

What carries the argument

The central object is a random weight process on vertices in a fixed degeneracy ordering, together with a martingale comparison and a change-of-measure identity. For a fixed target $v_k$, the paper runs a modified process in which every left-neighbor of $v_k$---a neighbour earlier in the order---is forced to take the multiplicative branch; triangle-freeness guarantees that no two left-neighbors of $v_k$ are adjacent, so their weights are never killed and form martingales. The change-of-measure identity relates the original and modified processes and gives $\mathrm{P}(v_k \in I)=\mathbb{E}[(1-e^{-w_0(v_k)e^X})e^{-X}]$, where $X$ is the sum of the modified left-neighbor weights. Markov's inequality bounds $X$ with probability at least $1/2$, and the choice $w_0\equiv (\ln d - 2\ln\ln d)/(2d)$ makes $w_0(v_k)e^X \le (1/2)\ln d$ on that event, yielding the uniform inclusion bound.

What would settle it

Find a sequence of triangle-free $d$-degenerate graphs $G_d$ with $d\to\infty$ and $\chi_f(G_d) > (4+\varepsilon) d/\ln d$ for some fixed $\varepsilon>0$; for example, solve the fractional chromatic number linear program on explicit high-girth or random sparse triangle-free constructions. Since the theorem is asymptotic, a single counterexample at one value of $d$ would not refute it.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: if $G$ is triangle-free and $d$-degenerate, then $\chi_f(G) \le (4+o(1))\, d/\ln d$, where the $o(1)$ term goes to $0$ as $d$ goes to infinity. The proof fixes a degeneracy ordering $v_1,\ldots,v_n$ and runs a random weight process: at step $i$, with probability $1-e^{-w(v_i)}$ the vertex $v_i$ joins the independent set $I$ and all weights of its later neighbours are set to $0$, while otherwise the later neighbours' weights are multiplied by $e^{w(v_i)}$. For each vertex $v_k$, the analysis gives $\mathrm{P}(v_k \in I) \ge (1/4-o(1))\ln d/d$, uniformly over vertices, and the fractional chromatic bound follows because $\chi_f(G)$ is the reciprocal of the best uniform inclusion probability. The same process is stated more generally in Theorem 1.3: for any triangle-free graph and any $p$ satisfying $p(v_i) \le \prod_{v_j \in N_L(v_i)} (1-p(v_j))$, where $N_L(v_i)$ is the set of neighbours of $v_i$ that appear earlier in the order, the random independent set includes $v_i$ with probability at least $\alpha p(v_i)$, with $\alpha=(1-e^{-1/2})/2 \approx 0.196$. Ordering vertices by decreasing degree and taking $p(v_i)=\Theta(\ln d(v_i)/d(v_i))$ recovers the local Shearer bound up to constants.

Load-bearing premise

The load-bearing premise is that the graph is triangle-free: the proof's martingale step fails if two left-neighbors of the same vertex are adjacent, because then one could kill the other's weight during the process and the probability identity would no longer yield the lower bound.

Editorial extensions

If this is right

The main conjecture is confirmed: every triangle-free $d$-degenerate graph has fractional chromatic number at most $(4+o(1))d/\ln d$, giving the first improvement over the trivial $O(d)$ bound.
The induced bipartite subgraph conjecture follows directly: every triangle-free graph of minimum degree $d$ has an induced bipartite subgraph of average degree at least $(1/4-o(1))\ln d$, hence of minimum degree $\Omega(\ln d)$.
For graphs with local triangle bound $y$, combining the theorem with a known lemma gives $\chi_f(G)=O(d/\ln(d^2/y))$, extending the result to locally sparse graphs.
The general Theorem 1.3 recovers, up to constant factors, the local Shearer bound when vertices are ordered by decreasing degree.
The optimal leading constant is now known to lie between $1/2$ and $4$, with $1$ conjectured as the true value.

Reading between the lines

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

The only place triangle-freeness enters is the martingale claim, so analogous bounds should hold for any vertex ordering in which left-neighbors of a vertex are pairwise non-adjacent; the local-triangle-bound result is a first step in that direction.
Theorem 1.3 can be read as a feasible-region statement: a target inclusion vector $p$ is realizable up to constant $\alpha$ by a random independent set whenever each $p(v_i)$ is at most the product of $(1-p(v_j))$ over earlier neighbors. This resembles a hard-core occupancy condition and may support sampling or approximate fractional-coloring algorithms for sparse triangle-free graphs.
If the leading constant is indeed $1$, the proof strategy would need to extract more from the distribution of $X$; the paper's remark that $\alpha$ can be raised to $1/4$ is a hint that the current analysis is not tight.

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

This is the real thing, and it deserves a serious referee. The paper proves Harris's conjecture with a (4+o(1)) d/ln d bound, and Theorem 1.3 is a genuinely broader statement that recovers the local Shearer bound. The proof technique is new to this area: a random weight process where the weights of left neighbors form a martingale, combined with a change-of-measure that expresses the inclusion probability as an expectation involving an exponential factor. That is not a routine tweak of existing methods.

The central lemma, Theorem 2.1, is proved carefully. Claims 2.2 through 2.6 all check out. In particular, the step that the stress-test note flags—replacing w_{i-1}(vi) with w_{k-1}(vi) for left neighbors of vk—is valid. Updates in the process only flow to right neighbors, so once we pass step i-1, no later step can touch vi. The concrete path example in the stress test is wrong: with ordering v1,v2,v3, step 2 updates v3, not v1, because v1 is not a right neighbor of v2. So the martingale identity and Claim 2.6 stand. The application to Theorem 1.2 is a direct substitution, and the derivation of the Esperet-Kang-Thomassé conjecture follows exactly as the reader's report says.

There are no serious soft spots. The constant 4 is probably not optimal, and the paper says so; Conjecture 1.4 about the optimal constant being 1 is clearly labeled as a conjecture. Remark 2.7 notes that the constant in Theorem 1.3 can likely be improved with more work. These are minor. The citation pattern is clean: Harris is cited as the source of the conjecture, and the few self-citations are comparisons with earlier work, not inputs to the argument. The proof is self-contained and does not assume any equivalent form of the target result.

This is a major within-field result: a well-known conjecture that had seen no asymptotic improvement over the trivial O(d) bound is now settled, with a compact and apparently correct proof. It belongs in a strong combinatorics journal. Send it to serious referees. I would be glad to see it cited and would bring it to a reading group.

Recommendation: accept after the usual refereeing, with attention to presentation and the exact constants, but no fundamental worry about the main argument.

Referee Report

1 major / 3 minor

Summary. The paper proves Harris's conjecture that every triangle-free d-degenerate graph has fractional chromatic number O(d/log d), with the explicit bound (4+o(1))d/log d. The proof introduces a random weight-propagation process that generates an independent set I, and establishes a lower bound (Theorem 2.1) on the probability that a fixed vertex vk belongs to I under a condition on the initial weights of its left neighbours. This yields Theorem 1.2 by taking constant weights, and also a more general local version (Theorem 1.3) that implies the local Shearer bound. As a corollary, the Esperet–Kang–Thomassé conjecture on dense induced bipartite subgraphs follows.

Significance. Resolving a long-standing conjecture with an elegant, self-contained argument gives this paper high significance. The proof is genuinely novel: it uses a change-of-measure identity and a martingale argument rather than the standard entropy or naive first-moment methods. Theorem 1.3 is a natural strengthening that is likely to be of independent interest. I carefully checked the potentially delicate steps (Claims 2.2–2.6) and they are correct. In particular, the equality in Claim 2.2 relating the sums of weights before and after the process is valid because updates in the process only flow from a vertex to its right neighbours (higher indices). The paper correctly derives the known implications for induced bipartite subgraphs, and the constants are computed correctly.

major comments (1)

[§2, Claim 2.2] A potential objection to the change-of-measure identity is that the exponent should involve the weight of each left neighbour vi just before its own step, not at time k-1. This concern does not land: in the process, step i only modifies the weights of right neighbours, i.e., vertices with larger index. Hence once all left neighbours of vi (which have index < i) have been processed, the weight of vi is fixed for the rest of the run up to step k-1. Therefore tilde-w_{i-1}(vi)=tilde-w_{k-1}(vi) for every vi in N_L(vk), and the equality in Claim 2.2 is valid. The counterexample on a 3-vertex path misidentifies the update direction: a later vertex vj with j>i cannot update vi, since that would require vi to be a right neighbour of vj, forcing j<i.

minor comments (3)

[Proof of Theorem 2.1] In the Markov inequality step, the sum is written as sum_{vi in N_L(vk)} w0(vk), which is inconsistent with Claim 2.4 and with the hypothesis of Theorem 2.1; it should read sum_{vi in N_L(vk)} w0(vi). The following line 'w0(vk)eX <= epsilon whenever X < 2 sum w0(vk)' has the same typo and should likewise read w0(vi) inside the sum.
[Throughout] The manuscript contains several typographical artifacts (e.g., 'interest ing' in the abstract, 'ga ve' in the introduction, 'for the sake or brevity' in Remark 2.7, and 'R. L. Brooks, R. L:' in reference [7]). These should be corrected during the revision process.
[Proof of Theorem 1.2] The step from the lower bound P(vk in I) >= (1/4-o(1)) ln d / d to the fractional chromatic number is clear, but it may be worth adding a sentence spelling out that one obtains an independent-set distribution with vertex probabilities at least this value, so that the reciprocal gives the claimed upper bound.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is self-contained and derives the theorem from a new Markov process without assuming its conclusion.

full rationale

The paper's central result, Theorem 1.2, is obtained from the explicit randomized process in Section 2. The proof of Theorem 2.1, and hence Theorems 1.2 and 1.3, uses only the process definition, elementary probability (including Markov's inequality), and elementary inequalities; no fitted parameters, no empirical data, and no renaming of a known result. The only self-citations, [23] and [24], are contextual comparisons: [24] is mentioned after Theorem 1.3 is proved directly and is not used as a premise. Harris's conjecture appears as the target statement, not as an input, and the Esperet-Kang-Thomassé implication is a downstream corollary. The degeneracy and triangle-free hypotheses enter exactly where the proof needs them (the left-neighbor martingale and |NL(vi)| <= d), and all inequalities are checked in the text. Even the reviewer's noted concern about the change-of-measure identity in Claim 2.2 is a possible technical error in the proof, not a circular dependence of the theorem on its own conclusion. The derivation chain is therefore self-contained.

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

The central claim is a universal statement over all triangle-free d-degenerate graphs. The proof uses only standard probability and graph theory facts; no empirical constants or invented entities appear. The initial weight w0 is an auxiliary choice in the proof, not a fitted parameter: the theorem holds for any positive weight assignment satisfying the hypothesis of Theorem 2.1, and the particular choice is made only to satisfy that hypothesis. The triangle-free condition is a domain assumption that is part of the theorem statement, not an additional unstated axiom.

assumptions (3)

standard math Standard probabilistic facts: expectation, Markov's inequality, martingales, and the elementary inequality 1-e^{-y} ≥ ((1-e^{-ε})/ε)y for 0≤y≤ε.
Used throughout the proof of Theorem 2.1 and Claims 2.2-2.6; these are unproved background results in probability.
standard math Every d-degenerate graph admits a vertex ordering in which each vertex has at most d earlier neighbors.
Invoked in the proof of Theorem 1.2 to bound |NL(vk)|≤d; this is a standard consequence of the definition of degeneracy.
standard math For p(vi) ∈ [0,1), exp(∑ p(vi)) ≤ ∏ (1-p(vi))^{-1}.
Used to derive Theorem 1.3 from the condition p(vi) ≤ ∏(1-p(vj)); follows from -ln(1-x) ≥ x for x∈[0,1).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Triangle-free $d$-degenerate graphs have small fractional chromatic number." pith.science (2026). https://pith.science/paper/EIT73TL4

@misc{pith2026250118238,
  author       = {Pith},
  title        = {Pith review of: Triangle-free $d$-degenerate graphs have small fractional chromatic number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EIT73TL4}},
  note         = {Machine review of arXiv:2501.18238}
}

abstract

A well-known conjecture by Harris states that any triangle-free $d$-degenerate graph has fractional chromatic number at most $O\left(\frac{d}{\ln d}\right)$. This conjecture has gained much attention in recent years, and is known to have many interesting implications, including a conjecture by Esperet, Kang and Thomass\'e that any triangle-free graph with minimum degree $d$ contains a bipartite induced subgraph of minimum degree $\Omega(\log d)$. Despite this attention, Harris' conjecture has remained wide open with no known improvement on the trivial upper bound, until now. In this article, we give an elegant proof of Harris' conjecture. In particular, we show that any triangle-free $d$-degenerate graph has fractional chromatic number at most $(4+o(1))\frac{d}{\ln d}.$ The conjecture of Esperet et al. follows as a direct consequence. We also prove a more general result, showing that for any triangle-free graph $G$, there exists a random independent set in which each vertex $v$ is included with probability $\Omega(p(v))$, where $p:V(G)\rightarrow [0,1]$ is any function that satisfies a natural condition.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 23 canonical work pages

[1]

N. Alon, M. Krivelevich, B. Sudakov: Coloring Graphs wit h Sparse Neighborhoods, Journal of Com- binatorial Theory, Series B, 77(1), 1999, 73–82

work page 1999
[2]

Anderson, A

J. Anderson, A. Bernshteyn, and A. Dhawan. Colouring gra phs with forbidden bipartite subgraphs. Combinatorics, Probability & Computing, 32(1), 2023, 45-– 67

work page 2023
[3]

Anderson, A

J. Anderson, A. Dhawan, and A. Kuchukova: Coloring local ly sparse graphs, arxiv preprint arXiv:2402.19271 [math.CO], 2024+

work page arXiv 2024
[4]

Bollob´ as: The independence ratio of regular graphs, Proc

B. Bollob´ as: The independence ratio of regular graphs, Proc. Amer. Math. Soc., 83 1981, 433-–436

work page 1981
[5]

Bonamy, T

M. Bonamy, T. Kelly, P. Nelson, and L. Postle: Bounding χ by a fraction of δ for graphs without large cliques. Journal of Combinatorial Theory, Series B, 1 57, 2022, 263—282

work page 2022
[6]

Bradshaw, B

P. Bradshaw, B. Mohar, and L. Stacho: Bipartite graphs ar e ( 4 5 − ǫ) ∆ log ∆ -choosable. arxiv preprint arXiv:2409.01513 [math.CO], 2024+

arXiv 2024
[7]

R. L. Brooks, R. L: On colouring the nodes of a network. Mat hematical Proceedings of the Cambridge Philosophical Society, 37(2), 1941, 194–197

work page 1941
[8]

Davies, M

E. Davies, M. Jenssen, W. Perkins, B. Roberts: On the aver age size of independent sets in triangle-free graphs. Proceedings of the American Mathematical Society 1 46(1), 2018, 111-–124

work page 2018

Show all 27 references

[9]

Davies, R

E. Davies, R. de Joannis de Verclos, R. J. Kang, and F. Piro t: Colouring triangle-free graphs with local list sizes, Randomised Structures & Algorithms, 57, 2 020, 730-–744
[10]

Davies, R

E. Davies, R. J. Kang, F. Pirot, J. Sereni: Graph structu re via local occupancy. arxiv preprint arXiv:2003.14361 [math.CO], 2020+. TRIANGLE-FREE d-DEGENERATE GRAPHS HA VE SMALL FRACTIONAL CHROMATIC NUMBER 7

2003 arXiv
[11]

Davies, R

E. Davies, R. J. Kang: The hard-core model in graph theor y. arxiv preprint arXiv:2501.03379 [math.CO], 2025+

2025 arXiv
[12]

B Descartes: Solution to advanced problem no. 4526. Ame rican Mathematical Monthly, 61(352), 1954, 216

1954
[13]

Esperet, R

L. Esperet, R. Kang, S. Thomass´ e: Separation choosabi lity and dense bipartite induced subgraphs, Combinatorics, Probability and Computing 28(5), 2019, 720 —732

2019
[14]

Harris: Some results on chromatic number as a funct ion of triangle count, SIAM Journal on Discrete Mathematics 33(1), 2019, 546-–563

D.G. Harris: Some results on chromatic number as a funct ion of triangle count, SIAM Journal on Discrete Mathematics 33(1), 2019, 546-–563

2019
[15]

Hurley, R

E. Hurley, R. de Joannis de Verclos, R. J. Kang: An improv ed procedure for colouring graphs of bounded local density. In Proceedings of the 2021 ACM-SIAM S ymposium on Discrete Algorithms (SODA), 2021, 135–148

2021
[16]

Hurley, F

E. Hurley, F. Pirot: Colouring locally sparse graphs wi th the ﬁrst moment method, arXiv preprint arXiv:2109.15215 [math.CO], 2021+

2021 arXiv
[17]

Hurley, F

E. Hurley, F. Pirot: Uniformly random colourings of spa rse graphs. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, 2023, 1357— 1370

2023
[18]

Janzer, R

B. Janzer, R. Steiner, B. Sudakov: Chromatic number and regular subgraphs. arxiv preprint arXiv:2410.02437 [math.CO], 2024+

2024 arXiv
[19]

Johansson: Asymptotic choice number for triangle fr ee graphs

A. Johansson: Asymptotic choice number for triangle fr ee graphs. Technical report, Technical report 91-5, DIMACS, 1996

1996
[20]

Kelly, L

T. Kelly, L. Postle: Fractional coloring with local dem ands and applications to degree-sequence bounds on the independence number, Journal of Combinatorial Theor y, Series B, 169, 2024, 298–337

2024
[21]

A. V. Kostochka, J. Neˇ setˇ ril: Properties of Descartes’ Construction of Triangle-Free Graphs with High Chromatic Number. Combinatorics, Probability and Computi ng. 8(5), 1999, 467–472

1999
[22]

M. Kwan, S. Letzter, B. Sudakov, T. Tran: Dense Induced B ipartite Subgraphs in Triangle-Free Graphs. Combinatorica 40, 2020, 283-–305

2020
[23]

Martinsson: A simpliﬁed proof of the Johansson-Moll oy Theorem using the Rosenfeld counting method, arxiv preprint arXiv:2111.06214 [math.CO]

A. Martinsson: A simpliﬁed proof of the Johansson-Moll oy Theorem using the Rosenfeld counting method, arxiv preprint arXiv:2111.06214 [math.CO]

arXiv
[24]

Martinsson, R

A. Martinsson, R. Steiner: Local Shearer bound. arxiv p reprint arXiv: arXiv:2501.00567 [math.CO], 2024+

2024 arXiv
[25]

Molloy: The list chromatic number of graphs with smal l clique number

M. Molloy: The list chromatic number of graphs with smal l clique number. Journal of Combinatorial Theory, Series B, 134, 2019, 264—284

2019
[26]

Pirot and J

F. Pirot and J. Sereni: Fractional chromatic number, ma ximum degree, and girth. SIAM Journal on Discrete Mathematics, 35(4), 2021, 2815–2843

2021
[27]

A. A. Zykov: On some properties of linear complexes. Mat ematicheskii sbornik, 66(2), 1949, 163-–188

1949

Pith tools

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

[1] [1]

N. Alon, M. Krivelevich, B. Sudakov: Coloring Graphs wit h Sparse Neighborhoods, Journal of Com- binatorial Theory, Series B, 77(1), 1999, 73–82

work page 1999

[2] [2]

Anderson, A

J. Anderson, A. Bernshteyn, and A. Dhawan. Colouring gra phs with forbidden bipartite subgraphs. Combinatorics, Probability & Computing, 32(1), 2023, 45-– 67

work page 2023

[3] [3]

Anderson, A

J. Anderson, A. Dhawan, and A. Kuchukova: Coloring local ly sparse graphs, arxiv preprint arXiv:2402.19271 [math.CO], 2024+

work page arXiv 2024

[4] [4]

Bollob´ as: The independence ratio of regular graphs, Proc

B. Bollob´ as: The independence ratio of regular graphs, Proc. Amer. Math. Soc., 83 1981, 433-–436

work page 1981

[5] [5]

Bonamy, T

M. Bonamy, T. Kelly, P. Nelson, and L. Postle: Bounding χ by a fraction of δ for graphs without large cliques. Journal of Combinatorial Theory, Series B, 1 57, 2022, 263—282

work page 2022

[6] [6]

Bradshaw, B

P. Bradshaw, B. Mohar, and L. Stacho: Bipartite graphs ar e ( 4 5 − ǫ) ∆ log ∆ -choosable. arxiv preprint arXiv:2409.01513 [math.CO], 2024+

arXiv 2024

[7] [7]

R. L. Brooks, R. L: On colouring the nodes of a network. Mat hematical Proceedings of the Cambridge Philosophical Society, 37(2), 1941, 194–197

work page 1941

[8] [8]

Davies, M

E. Davies, M. Jenssen, W. Perkins, B. Roberts: On the aver age size of independent sets in triangle-free graphs. Proceedings of the American Mathematical Society 1 46(1), 2018, 111-–124

work page 2018