Local Shearer bound

Anders Martinsson; Raphael Steiner

REVIEW 1 major objections 4 minor 1 cited by

Local Shearer bound

T0 review · 1 major / 4 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 Every triangle-free graph admits a probability distribution on independent sets that contains each degree-$d$ vertex with probability at least $(1-o(1))\ln d/d$.

desk verdict A serious and likely correct line of attack on two 2018 conjectures, but the proof of the key weighted theorem has an unproven sign step that needs repair. read the letter →

arxiv 2501.00567 v1 pith:HZORBK4B submitted 2024-12-31 math.CO

Anders Martinsson , Raphael Steiner This is my paper · ORCID

classification math.CO MSC 05C1505C3505C6905C50

keywords triangle-freegraphsindependencenumberfractionalchromaticShearerboundlocaldemandsspectralradiusindependentsetsweightedgraphcoloring

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

The paper proves a local, degree-by-degree strengthening of Shearer's independence bound: in every triangle-free graph, one can choose a probability distribution over independent sets so that each vertex $v$ is included with probability at least $(1-o(1))\ln d(v)/d(v)$, where $d(v)$ is its degree. This is exactly the guarantee conjectured in 2018 for fractional coloring with local demands. As a consequence the paper confirms the predicted bound $\chi_f(G)\le(\sqrt{2}+o(1))\sqrt{n/\ln n}$ for $n$-vertex triangle-free graphs, proves an analogous bound in terms of the number of edges, and obtains a spectral bound $\chi_f(G)\le(1+o(1))\rho(G)/\ln\rho(G)$. A weighted version of the result is the engine behind all four applications.

What carries the argument

The carrying object is the function $f(x)$, the continuous extension of $(1-x+x\ln x)/(x-1)^2$ to $[0,\infty)$, with $f(0)=1$, $f(1)=1/2$, and $f(x)=(1-o(1))\ln x/x$ as $x\to\infty$; it satisfies the differential equation $x(x-1)f'(x)+(x+1)f(x)=1$. The proof of Theorem 2.1 inducts on the number of vertices, maintaining the smallest possible uniform slack $\delta_0$. At the contradiction step it perturbs weights by $w'(v)=w(v)\exp(\varepsilon w(N_G(v)))$ and mixes the distribution on $G$ with distributions on $G-N_G[u]$, using convexity of $f$ and the differential equation to make all lower-order terms cancel.

What would settle it

Take a triangle-free graph and positive weights with $w(N_G(v))>w(v)$ at some vertex $v$, and check the sign of $x f'(x) z-2\varepsilon^2$ with $x=w(N_G(v))/w(v)$ and $z=\varepsilon(w(v)-w(N_G(v)))$ for small $\varepsilon$; when it is positive, the inequality before "Rearranging yields" in the proof is invalid, so the stated weighted theorem would need a different argument.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2.1: for every triangle-free graph $G$ and every strictly positive vertex weight function $w$, there exists a probability distribution on the independent sets of $G$ with $\mathbb{P}_{I\sim D}[v\in I]\ge f(w(N_G(v))/w(v))$ for all $v$, where $f$ is Shearer's function, the continuous extension of $(1-x+x\ln x)/(x-1)^2$. The all-weights-one case gives the local Shearer bound of Theorem 1.2, and choosing weights from a Perron–Frobenius eigenvector gives the spectral bound. The authors view the weighted theorem as the real contribution, from which the $n$-vertex, edge, and spectral bounds follow by short arguments.

Load-bearing premise

The load-bearing premise is that a certain error term at the single vertex that violates the claimed probability is automatically nonpositive; the paper does not prove this sign condition, and it can fail when a vertex's neighborhood carries more total weight than the vertex itself.

Editorial extensions

If this is right

The local demand version of fractional coloring is confirmed: each vertex $v$ can be assigned a measurable subset of $[0,1]$ of measure $(1-o(1))\ln d(v)/d(v)$ so that adjacent vertices receive disjoint subsets.
The fractional chromatic number of every $n$-vertex triangle-free graph is at most $(\sqrt{2}+o(1))\sqrt{n/\ln n}$, matching the conjectured maximum.
For triangle-free graphs with $m$ edges, the fractional chromatic number is at most $(18^{1/3}+o(1))m^{1/3}/(\ln m)^{2/3}$, close to the conjectured $16^{1/3}$ version.
Every triangle-free graph satisfies $\chi_f(G)\le (1+o(1))\rho(G)/\ln\rho(G)$, saving a logarithmic factor over the classical spectral bound on the chromatic number.
The all-ones and Perron–Frobenius weight choices recover the original Shearer bound and the spectral bound from the same weighted theorem.

Reading between the lines

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

The sign condition that appears unproved in Theorem 2.1 may be repairable by letting $\varepsilon$ shrink with $x-1$ or by using a higher-order Taylor expansion; whether the weighted theorem survives this repair is independent of the truth of its corollaries.
The spectral proof only uses triangle-freeness to keep neighborhoods disjoint; the same eigenvector-weighting trick may extend to $K_{r+1}$-free graphs with the corresponding Shearer-type function.
The paper's existential compactness argument suggests an LP formulation; an efficient rounding algorithm for the independent-set distribution would make the local bound algorithmic, which the current proof does not provide.
Because the theorem's applications rely only on two specific weight choices, a counterexample to the full weighted statement would not necessarily refute any of Theorems 1.2, 1.4, 1.5, or 1.6.

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

What you should know: this paper claims the local Shearer bound, resolving Kelly–Postle's main conjecture and the Cames van Batenburg et al. conjecture on fractional chromatic number, plus a spectral-radius bound. The structure is sound: all the corollaries (Theorems 1.2, 1.4, 1.5, 1.6) follow from the weighted Theorem 2.1, and I checked those derivations—they are clean and plausible. The weighted theorem itself is genuinely new, and the induction-plus-LP compactness argument is a natural and clever framework. The spectral application is a nice touch, not a routine extension.

The problem is in the proof of Theorem 2.1. After the Taylor estimate, the authors have a lower bound of the form (1 − εa)(f(x)+T), with T = x f'(x) z − 2ε². They replace this by f(x)+T−εa f(x), dropping the term −εa T. That is valid only if T ≤ 0. The text puts an underbrace '<0' on the bracket, but no proof. And it is not generally true: take x = 3, w(v)=0.2, w(N(v))=0.6, ε=0.01; then z = −0.004, f'(3)≈−0.0493, and T≈3.9·10⁻⁴ > 0. This is a legitimate configuration in a triangle-free graph (e.g., a leaf with a heavy neighbor and one other vertex). So the displayed inequality does not hold as written. The final contradiction δ0²/8 > δ0²/8 depends exactly on that step.

I don't see anything in the choice of the violating vertex that forces T ≤ 0. The proof of Theorem 2.1 is therefore not established as written. The gap is load-bearing, but I would not call the paper incoherent or the approach hopeless. The rest of the writing is careful, the literature is handled honestly, and the corollary work shows real skill. The likely fix is to handle positive T separately or to modify the random process/choice of ε; my guess is the result is true.

Verdict: this deserves serious refereeing, not a desk reject. Send it out, but the referee should demand a repaired sign argument. I would not cite the weighted theorem as a proven result until that appears; the conjecture resolutions are conditional on it.

Referee Report

1 major / 4 minor

Summary. The paper proves a local strengthening of Shearer's independence bound for triangle-free graphs: for every triangle-free graph there is a probability distribution on its independent sets such that each vertex v is included with probability (1-o(1)) ln d(v)/d(v). The proof is organized around a weighted technical theorem, Theorem 2.1, proved by induction together with a compactness/linear-programming argument. From Theorem 2.1 the authors derive the conjectured fractional chromatic number bound of Cames van Batenburg et al. for n-vertex triangle-free graphs, an edge-count analogue, and the spectral bound chi_f(G) <= (1+o(1)) rho(G)/ln rho(G).

Significance. If the main theorem is correct, it resolves a 2018 conjecture of Kelly and Postle and confirms the subsequent conjectures of Cames van Batenburg et al.; the spectral application is also a natural and notable strengthening of the fractional version of Molloy's bound. The deduction of Theorems 1.2, 1.4, 1.5, and 1.6 from Theorem 2.1 is clean and mostly self-contained, with no fitted parameters. The key proof is, however, invalid at a load-bearing sign step, as detailed below.

major comments (1)

[Section 2, proof of Theorem 2.1] The displayed chain immediately after 'Plugging this estimate into the above lower bound' replaces (1 - epsilon a)(f(x) + T) by f(x) + T - epsilon a f(x), where a = w(v) + w(N_G(v)) and T = x z f'(x) - 2 epsilon^2. This is a valid lower bound only if T <= 0, as the manuscript's underbrace '<0' asserts. No proof of T <= 0 is given, and the assertion is not generally true for the admissible positive weight assignments: for example, with w(v) = 0.2, w(N_G(v)) = 0.6 (so x = 3), and epsilon = 0.01, one has z = -0.004, f'(3) approximately -0.0493, and T approximately 3.9 x 10^-4 > 0. Such weights are compatible with the proof because the weights are arbitrary strictly positive functions normalized to total weight 1. The subsequent 'Rearranging yields' step and the final contradiction delta_0^2/8 > delta_0^2/8 rely exactly on this sign: if T > 0, the same computation gives delta_0^2/8 > delta_0^2/8 - epsilon a T, which is true rather than absurd. Since the proof of Theorem 2.1 neither derives T <= 0 from the choice of the violating vertex nor offers an alternative argument, Theorem 2.1 is not established as written.

minor comments (4)

[Section 2 and Theorem 2.1] The notation N_G is overloaded: in the statement of Theorem 2.1 it denotes the open neighborhood, while in the proof N_G(u) is explicitly redefined as the closed neighborhood. This makes later expressions such as x in V(G) \ N_G(v) ambiguous and should be clarified.
[Section 2, proof of the Claim] In the Claim, the inequality replacing 1/(1 - epsilon w(N_G(v))) by 1 uses that w(N_G(y)) - w(v) >= 0 for y in N_G(v); this follows from v in N_G(y) and positivity of w, but it is not stated and should be made explicit.
[Proof of Theorem 1.6] There is a typographical error in the line 'chi_f(G) <= 1/f(rho(G)))': an extra closing parenthesis appears after rho(G).
[Abstract] The abstract contains several typographical artifacts, including 'W e' and 'cl assic'; these should be corrected in the final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main proof is a self-contained induction and linear-programming argument, and prior results are used only as downstream applications, not as inputs to the key theorem.

full rationale

The paper's central result, Theorem 2.1, is proved by induction on the number of vertices, using the previously established Shearer function f and its elementary properties. The proof sets up a compact set K of slack parameters and derives a contradiction from the assumption that its minimum δ0 is positive. No parameter is fitted to the target data, and no 'prediction' is renamed from an input. The distribution D′ is constructed explicitly from the induction hypothesis and the assumed distribution D, and the contradiction is algebraic. The use of Kelly and Postle's Proposition 3.1 occurs only in the proof of Theorem 1.4, after Theorem 1.2 has already been established via Theorem 2.1, and it is not a self-citation by the present authors. The various deductions in Section 3 are straightforward applications of Theorem 2.1 or Theorem 1.2. There is no self-definitional reduction, no fitted input called a prediction, and no load-bearing self-citation. A possible gap in the proof of Theorem 2.1 concerning a dropped term of uncertain sign is a correctness concern, not a circularity concern: even if the step were unjustified, it would not make the theorem an input to itself. The paper is self-contained against external benchmarks, so the appropriate circularity score is 0.

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

No fitted constants appear in the results. The main theorem rests on standard analytic properties of Shearer's function and linear-programming compactness. The proof also implicitly assumes a sign condition in its final algebraic step; this is an ad hoc and unproved assumption.

assumptions (4)

standard math Shearer's function f is convex, decreasing, differentiable on (0, infinity), satisfies x(x-1)f'(x)+(x+1)f(x)=1, and |x f'(x)|<1.
Stated in Section 2 as 'It is not hard to check'; elementary but a nontrivial input to the proof.
standard math The linear program defining K_w is feasible and bounded, and K is compact so the minimum delta_0 is attained.
Used in Section 2 to define delta_0 and to apply the induction hypothesis.
standard math Perron-Frobenius theorem for nonnegative matrices yields a positive eigenvector for a connected graph.
Used to prove Theorem 1.6 from Theorem 2.1 by taking the Perron vector as the weight function.
ad hoc to paper Unstated sign condition x f'(x) z - 2 epsilon^2 <= 0 at the violated vertex.
The displayed inequality before 'Rearranging yields' appears to require this sign; it is not proved and is false for some positive weight assignments, so the central proof depends on an unjustified assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Local Shearer bound." pith.science (2026). https://pith.science/paper/HZORBK4B

@misc{pith2026250100567,
  author       = {Pith},
  title        = {Pith review of: Local Shearer bound},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HZORBK4B}},
  note         = {Machine review of arXiv:2501.00567}
}

abstract

We prove the following local strengthening of Shearer's classic bound on the independence number of triangle-free graphs: For every triangle-free graph $G$ there exists a probability distribution on its independent sets such that every vertex $v$ of $G$ is contained in a random independent set drawn from the distribution with probability $(1-o(1))\frac{\ln d(v)}{d(v)}$. This resolves the main conjecture raised by Kelly and Postle (2018) about fractional coloring with local demands, which in turn confirms a conjecture by Cames van Batenburg et al. (2018) stating that every $n$-vertex triangle-free graph has fractional chromatic number at most $(\sqrt{2}+o(1))\sqrt{\frac{n}{\ln(n)}}$. Addressing another conjecture posed by Cames van Batenburg et al., we also establish an analogous upper bound in terms of the number of edges. To prove these results we establish a more general technical theorem that works in a weighted setting. As a further application of this more general result, we obtain a new spectral upper bound on the fractional chromatic number of triangle-free graphs: We show that every triangle-free graph $G$ satisfies $\chi_f(G)\le (1+o(1))\frac{\rho(G)}{\ln \rho(G)}$ where $\rho(G)$ denotes the spectral radius. This improves the bound implied by Wilf's classic spectral estimate for the chromatic number by a $\ln \rho(G)$ factor and makes progress towards a conjecture of Harris on fractional coloring of degenerate graphs.

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

Triangle-free $d$-degenerate graphs have small fractional chromatic number
math.CO 2025-01 accept novelty 8.0 of 10

Every triangle-free d-degenerate graph has fractional chromatic number at most (4+o(1))d/ln d, confirming Harris's conjecture.

Reference graph

Works this paper leans on

46 extracted references · 42 canonical work pages · cited by 1 Pith paper

[1]

N. Alon. Independence numbers of locally sparse graphs a nd a Ramsey type problem. Random Structures & Algorithms , 9(3):271–278, 1996

work page 1996
[2]

N. Alon, M. Krivelevich, and B. Sudakov. Coloring graphs with sparse neighborhoods. Journal of Combi- natorial Theory, Series B , 77(1):73–82, 1999

work page 1999
[3]

Anderson, A

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

work page 2023
[4]

Anderson, A

J. Anderson, A. Dhawan, and A. Kuchukova. Coloring local ly sparse graphs, 2024. URL: https://arxiv.org/abs/2402.19271, arXiv:2402.19271

arXiv 2024
[5]

B´ ar´ any

J. B´ ar´ any. A short proof of Kneser’s conjecture.Journal of Combinatorial Theory, Series A , 25(3):325–326, 1978

work page 1978
[6]

Bernshteyn, T

A. Bernshteyn, T. Brazelton, R. Cao, and A. Kang. Countin g colorings of triangle-free graphs. Journal of Combinatorial Theory, Series B , 161:86–108, 2023

work page 2023
[7]

Y. Bilu. Tales of Hoﬀman: Three extensions of Hoﬀman’s bo und on the graph chromatic number. Journal of Combinatorial Theory, Series B , 96(4):608–613, 2006. 10 ANDERS MARTINSSON AND RAPHAEL STEINER

work page 2006
[8]

Bohman and P

T. Bohman and P. Keevash. Dynamic concentration of the tr iangle-free process. Random Structures & Algorithms, 58(2):221–293, 2021

work page 2021

Show all 46 references

[9]

Bollob´ as

B. Bollob´ as. The independence ratio of regular graphs. Proceedings of the American Mathematical Society , 83:433—436, 1981

1981
[10]

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 , 157:263–282, 2022

2022
[11]

Bradshaw, B

P. Bradshaw, B. Mohar, and L. Stacho. Bipartite graphs a re ( 4 5 − ε) ∆ log ∆ -choosable, 2024. URL: https://arxiv.org/abs/2409.01513, arXiv:2409.01513

2024 arXiv
[12]

Cames van Batenburg, R

W. Cames van Batenburg, R. de Joannis de Verclos, R. J. Ka ng, and F. Pirot. Bipartite induced density in triangle-free graphs. The Electronic Journal of Combinatorics , 27(2):P2–34, 2020

2020
[13]

F. R. K. Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997

1997
[14]

Cvetkovic

D. Cvetkovic. Chromatic number and the spectrum of a gra ph. Publ. Inst. Math.(Beograd) , 14(28):25–38, 1972

1972
[15]

Davies, R

E. Davies, R. de Joannis de Verclos, R. J. Kang, and F. Pir ot. Coloring triangle-free graphs with local list sizes. Random Structures & Algorithms , 57(3):730–744, 2020

2020
[16]

Davies, R

E. Davies, R. de Joannis de Verclos, R. J. Kang, and F. Pir ot. Occupancy fraction, fractional colouring, and triangle fraction. Journal of Graph Theory , 97(4):557–568, 2021

2021
[17]

Davies and F

E. Davies and F. Illingworth. The χ-Ramsey problem for triangle-free graphs. SIAM Journal on Discrete Mathematics, 36(2):1124–1134, 2022

2022
[18]

Davies, M

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

2018
[19]

Davies, R

E. Davies, R. J. Kang, F. Pirot, and J. Sereni. Graph stru cture via local occupancy, 2020. URL: https://arxiv.org/abs/2003.14361, arXiv:2003.14361

2020 arXiv
[20]

A. Dhawan. Bounds for the independence and chromatic nu mbers of locally sparse graphs, 2024. arXiv:2403.03054

2024 arXiv
[21]

Dvoˇ r´ ak, J

Z. Dvoˇ r´ ak, J. Sereni, and J. Volec. Subcubic triangle-free graphs have fractional chromatic number at most 14/5. Journal of the London Mathematical Society , 89(3):641–662, 2014

2014
[22]

P. Erd˝ os. Some unsolved problems. Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., pages 221–254, 1961

1961
[23]

Erd˝ os and A

P. Erd˝ os and A. Hajnal. Chromatic number of ﬁnite and in ﬁnite graphs and hypergraphs. Discrete Mathematics, 53:281–285, 1985

1985
[24]

Esperet, R

L. Esperet, R. J. Kang, and S. Thomass´ e. Separation cho osability and dense bipartite induced subgraphs. Combinatorics, Probability & Computing , 28(5):720–732, 2019

2019
[25]

Fiz Pontiveros, S

G. Fiz Pontiveros, S. Griﬃths, and R. Morris. The triang le-free process and the Ramsey number R(3, k). Memoirs of the American Mathematical Society , 263:125 pp, 2020

2020
[26]

Guo and S

K. Guo and S. Spiro. New eigenvalue bound for the fractio nal chromatic number. Journal of Graph Theory , 106(1):167–181, 2024

2024
[27]

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

2019
[28]

T. P. Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. In 2006 47th Annual IEEE Symposium on Foundations of Computer Scien ce (FOCS’06), pages 39–46. IEEE, 2006

2006
[29]

A. J. Hoﬀman. On eigenvalues and colorings of graphs. Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, W is., 1969) , 1970

1969
[30]

R. A. Horn and C. R. Johnson. Matrix analysis . Cambridge university press, 2012

2012
[31]

Hurley, R

E. Hurley, R. de Joannis de Verclos, and R. J. Kang. An imp roved procedure for colouring graphs of bounded local density. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algo rithms (SODA) , pages 135–148. SIAM, 2021

2021
[32]

Hurley and F

E. Hurley and F. Pirot. Uniformly random colourings of s parse graphs. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC 2023, page 1357–1370, New York, NY, USA, 2023. Association for Computing Machinery

2023
[33]

Johansson

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

1996
[34]

D. Kang, D. K¨ uhn, A. Methuku, and D. Osthus. Graph and hy pergraph colouring via nibble methods: A survey. Proceedings of the 8th European Congress of Mathematics , pages 771–823, 2023

2023
[35]

Kelly and L

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

2024
[36]

M. Kwan, S. Letzter, B. Sudakov, and T. Tran. Dense induc ed bipartite subgraphs in triangle-free graphs. Combinatorica, 40(2):283–305, 2020

2020
[37]

Kwan and Y

M. Kwan and Y. Wigderson. The inertia bound is far from ti ght. Bulletin of the London Mathematical Society, 56(10):3196–3208, 2024

2024
[38]

Lov´ asz

L. Lov´ asz. Kneser’s conjecture, chromatic number, an d homotopy. Journal of Combinatorial Theory, Series A, 25(3):319–324, 1978. LOCAL SHEARER BOUND 11

1978
[39]

B. Mohar. Eigenvalues and colorings of digraphs. Linear Algebra and its Applications , 432(9):2273–2277, 2010

2010
[40]

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

2019
[41]

Nikiforov

V. Nikiforov. Chromatic number and spectral radius. Linear algebra and its applications , 426(2-3):810–814, 2007

2007
[42]

Pirot and J

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

2021
[43]

E. R. Scheinerman and D. H. Ullman. Fractional graph theory: a rational approach to the theory o f graphs. Dover publications Inc., 2011

2011
[44]

J. B. Shearer. A note on the independence number of trian gle-free graphs. Discrete Mathematics, 46(1):83– 87, 1983

1983
[45]

J. B. Shearer. A note on the independence number of trian gle-free graphs, II. Journal of Combinatorial Theory, Series B , 53(2):300–307, 1991

1991
[46]

H. S. Wilf. The eigenvalues of a graph and its chromatic n umber. Journal of the London Mathematical Society, s1-42(1):330–332, 1967

1967

Pith tools

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

[1] [1]

N. Alon. Independence numbers of locally sparse graphs a nd a Ramsey type problem. Random Structures & Algorithms , 9(3):271–278, 1996

work page 1996

[2] [2]

N. Alon, M. Krivelevich, and B. Sudakov. Coloring graphs with sparse neighborhoods. Journal of Combi- natorial Theory, Series B , 77(1):73–82, 1999

work page 1999

[3] [3]

Anderson, A

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

work page 2023

[4] [4]

Anderson, A

J. Anderson, A. Dhawan, and A. Kuchukova. Coloring local ly sparse graphs, 2024. URL: https://arxiv.org/abs/2402.19271, arXiv:2402.19271

arXiv 2024

[5] [5]

B´ ar´ any

J. B´ ar´ any. A short proof of Kneser’s conjecture.Journal of Combinatorial Theory, Series A , 25(3):325–326, 1978

work page 1978

[6] [6]

Bernshteyn, T

A. Bernshteyn, T. Brazelton, R. Cao, and A. Kang. Countin g colorings of triangle-free graphs. Journal of Combinatorial Theory, Series B , 161:86–108, 2023

work page 2023

[7] [7]

Y. Bilu. Tales of Hoﬀman: Three extensions of Hoﬀman’s bo und on the graph chromatic number. Journal of Combinatorial Theory, Series B , 96(4):608–613, 2006. 10 ANDERS MARTINSSON AND RAPHAEL STEINER

work page 2006

[8] [8]

Bohman and P

T. Bohman and P. Keevash. Dynamic concentration of the tr iangle-free process. Random Structures & Algorithms, 58(2):221–293, 2021

work page 2021