Pith. sign in

REVIEW 4 minor 31 references

Sharp bounds for the fractional chromatic number of high-girth $d$-degenerate graphs

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read For every large d, every 4-cycle-free d-degenerate graph has fractional chromatic number at most (1+o(1))d/log d, and there exist d-degenerate graphs of any fixed girth meeting this bound; an efficient randomized algorithm finds the colorin

desk verdict Solid, important paper: sharp fractional chromatic bounds for d-degenerate C4-free graphs and matching high-girth lower bounds; only real issue is an overstated heuristic remark in the abstract. read the letter →

arxiv 2607.26271 v1 pith:FWBGFFMQ submitted 2026-07-28 math.CO cs.DM

Peter Allen , Abhishek Dhawan , Jonathan A. Noel This is my paper · ORCID
classification math.COcs.DM MSC 05C1505C8005C85
keywords fractionalchromaticnumberd-degenerategraphsC4-freegirthrandomizedalgorithmuniformattachmentmodelLPdualityclique
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 aims to pin down the exact leading constant in the fractional chromatic number of d-degenerate graphs with no short cycles. It proves that every d-degenerate graph with no 4-cycles has fractional chromatic number at most (1+o(1))d/log d, and that this bound is witnessed by a polynomial-time randomized algorithm that actually outputs the fractional coloring. It also constructs d-degenerate graphs of arbitrarily large fixed girth whose fractional chromatic number is at least (1−o(1))d/log d, using a random uniform-attachment graph and an explicit fractional clique. Together these results confirm the conjectured sharp constant 1 for girth at least 5 and resolve the lower-bound half of the Martinsson–Steiner conjecture in a stronger form. The paper further explains why this random model has no algorithmic gap of the kind conjectured for bounded-degree triangle-free graphs.

What carries the argument

Upper bound: Algorithm 1, a randomized independent-set sampler that processes vertices in degeneracy order and maintains a weight p_i(v) starting at α=(log d)/((1+ε/2)d). Updates are designed so E[p_i(v) | past]=p_{i−1}(v), with a threshold p̂=d^{−ε/20} and equalizing coin flips that restore the martingale when a weight would exceed the threshold; vertices at the threshold are never selected. The analysis uses the supermartingale S_i = p_i(v_k)^2 ∏_{i<j≤k−1, v_j∈N_L(v_k)} (1+(1+(1+2η_{i,j,k})ε′)p_i(v_j)), where η_{i,j,k}=|N_L(v_j)∩N_L(v_k)∩{v_{i+1},...,v_{j−1}}|; 4-cycle-freeness forces η∈{0,1} and |N_R(v_i)∩N_L(v_k)|≤1, yielding E[p_{k−1}(v_k)^2]≤α^2 exp((1+o(1))dα). Lower bound: the unifor

What would settle it

Simulate Algorithm 1 many times on a large 4-cycle-free d-degenerate graph, and check that every vertex is selected with frequency at least (1−ε/40)log d/((1+ε/2)d); Theorem 1.3 predicts this for all vertices. A sharper test targets the structural premise: start from an otherwise 4-cycle-free graph and add a single Co-Neighbor Path 4-cycle (two early vertices whose later neighborhoods share a common pair), then measure the selection probability of the affected late vertex; the paper's analysis says this is precisely where the supermartingale inequality can fail, so a constant-factor drop in in

Watch

Extended reading notes

Core claim

The central claim is that the sharp constant 1 in the Martinsson–Steiner conjecture is correct for graphs of girth at least 5, and that the lower bound holds with arbitrarily large fixed girth. Concretely, Theorem 1.3 says that for each ε>0 and all large d, every n-vertex d-degenerate C4-free graph satisfies χ_f(G)≤(1+ε)d/log d, with a poly(n,d)-time randomized algorithm that outputs, with high probability, an (α,q)-coloring at weight (1+ε)d/log d. The proof runs a weight-thresholding independent-set sampler in degeneracy order; C4-freeness enters exactly where the analysis needs |N_R(v_i)∩N_L(v_k)|≤1, which controls the second moment of the sampler's weights. Theorem 1.4 says that for fixed

Load-bearing premise

The load-bearing premise is 4-cycle-freeness: the proof needs that for every pair of vertices v_i and v_k, the set of right-neighbors of v_i that are also left-neighbors of v_k has size at most 1, because this is what keeps the second-moment supermartingale from drifting upward; without it—even in a triangle-free graph with one Co-Neighbor Path 4-cycle—a vertex's selection probability can drop by a constant factor and the upper bound collapses.

Editorial extensions

If this is right

  • The upper bound is constructive: for any 4-cycle-free d-degenerate graph, a polynomial-time randomized algorithm outputs an explicit fractional coloring of weight (1+o(1))d/log d with high probability, so the sharp bound is not merely existential.
  • The lower-bound construction fixes the leading constant: no upper bound of the form cd/log d with c<1 can hold for all d-degenerate graphs of girth at least 4, since the constructed graphs reach (1−o(1))d/log d.
  • The lower-bound half of the Martinsson–Steiner conjecture is resolved in a stronger form: the lower-bound examples can have arbitrary constant girth g≥4, not just triangle-freeness.
  • As the paper notes, a corollary of the upper bound via an earlier result is that every 4-cycle-free graph with minimum degree d contains an induced bipartite subgraph with average degree at least (1−o(1))log d.
  • In the uniform attachment model the fractional chromatic number is asymptotically d/log d and matches the algorithmic upper bound, so this random model does not exhibit the conjectured factor-2 algorithmic gap for bounded-degree triangle-free graphs.

Reading between the lines

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

  • The obstacle to the full triangle-free conjecture is pinpointed as the Co-Neighbor Path configuration of a 4-cycle in the degeneracy ordering; we conjecture that a proof of the sharp bound under a mild codegree condition, as posed in Problem 4.1, would carry over to all triangle-free d-degenerate graphs and unify the result with recent codegree-based independence bounds.
  • Because the paper's lower-bound graph is built from uniform attachment, the harmonic-tail fractional clique is essentially a statement about age-biased random graphs; we suspect the same dual construction gives χ_f=(1+o(1))d/log d for any model in which each new vertex connects to uniformly random earlier vertices, suggesting the threshold is robust to details of the model.
  • The second-moment supermartingale technique, which controls the probability that the sampler's weights hit the threshold, seems transferable to other algorithmic random-weight settings such as list fractional coloring or K_{t,t}-free graphs as in Problem 4.2, although the paper does not develop those extensions.
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.

Referee Report

0 major / 4 minor

Summary. The paper proves sharp bounds for the fractional chromatic number of sparse degenerate graphs. Theorem 1.3 shows that every n-vertex d-degenerate C4-free graph satisfies χ_f(G) ≤ (1+ε)d/log d for large d, via a poly(n,d)-time randomized algorithm that outputs a fractional coloring of that weight. This confirms the Martinsson–Steiner upper-bound conjecture under the additional C4-free (girth at least 5) hypothesis. Theorem 1.4 constructs, for every g ≥ 4 and δ > 0, a d-degenerate graph with girth at least g and χ_f(G) ≥ (1−δ)d/(W(d)+1), confirming the matching lower bound in a stronger form. The lower bound is proved by analyzing a uniform-attachment random graph, using the LP dual (fractional clique) with an explicit harmonic-tail weight function, and then deleting one vertex from each short cycle.

Significance. If correct, the paper substantially advances the Martinsson–Steiner program: it gives the optimal leading constant for the fractional chromatic number of C4-free d-degenerate graphs, and it confirms the conjectured lower bound for all triangle-free degenerate graphs, in fact for every fixed girth g ≥ 4. A notable strength is that the upper-bound proof is fully constructive and yields an efficient randomized algorithm with an explicit O_ε(d log n / log d)-size witness. The lower bound is self-contained and uses no fitted parameters; the LP-duality certificate is explicit. The paper also correctly identifies the structural role of C4-freeness in the supermartingale analysis. The computational-complexity discussion in Section 4 is explicitly heuristic, and the main theorems do not depend on it. Overall this is a solid, significant contribution.

minor comments (4)
  1. [§2, proof of Lemma 2.2] In the deterministic inequalities used in the final cases of the supermartingale proof, the justification is stated as '0 ≤ p_{i-1}(v_i) ≤ p̂ ≤ ε/40'. This alone does not imply 1/(1−x) ≤ 1 + (1+ε')x for x as large as ε/40; the needed condition is roughly x ≤ ε'/2, i.e. p̂ ≤ ε/120. The actual p̂ = d^{-ε/20} is much smaller than this for d ≥ d0 by the displayed choice of d0, so the argument is repairable, but the proof should state the stronger bound on p̂ explicitly and derive it from the d0 condition.
  2. [§2, proof of Lemma 2.2, second easy case] The sentence 'If v_i ∉ N_L(X∪{v_k}), or v_i ∈ N_L(X)∩B_{i-1}, ... we get S_i = S_{i-1}' is not correct in the subcase v_i ∈ N_L(v_k) ∩ N_L(X) ∩ B_{i-1}: the factor for v_i in the product defining S_{i-1} disappears when passing to S_i, so S_i < S_{i-1}. The desired supermartingale inequality S_i ≤ S_{i-1} still holds, so the proof is unaffected once this is corrected.
  3. [Abstract and §4] The abstract states that the results 'reveal that this model lacks the typical computational complexity barriers found in Erdős–Rényi graphs.' Section 4 explicitly characterizes the relevant discussion as 'quite heuristic' and does not prove any algorithmic lower bound. I recommend softening the abstract to say that the model does not exhibit the conjectured barrier for this algorithm, or that the observation is heuristic.
  4. [Theorem 1.3] The definition q = ceil(400^2 · 20 ε^{-4} d log n / log d) gives q = 0 when n = 1. The theorem is trivial for n = 1, but for formal correctness one should take q = max(1, ...).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: both main theorems are proved from explicit constructions and self-contained analyses.

full rationale

The upper bound (Theorem 1.3) is derived by defining Algorithm 1 in full, with explicit parameters α = log d / ((1+ε/2)d) and p̂ = d^{-ε/20}, and then proving the needed martingale property (Lemma 2.1) and the key concentration estimate (Lemma 2.2). The C4-freeness hypothesis is used explicitly and locally: it implies η_{i,j,k} ∈ {0,1} and |N_R(v_i) ∩ N_L(v_k)| ≤ 1, which is exactly what makes the sequence S_i a supermartingale. No fitted parameter, no data-dependent constant, and no invocation of the target theorem or the conjectured bound enters the proof. The algorithm is credited to Dhawan [11], but the paper contains both the full algorithm and its analysis, so the citation is attribution, not a load-bearing imported result. The lower bound (Theorem 1.4) is an independent construction: U_{n,d} is d-degenerate by its ordering, the function f is an explicit fractional clique candidate built from harmonic tails, Lemma 3.2 bounds the probability of independent sets with large ℓ_n-weight, Lemma 3.3 bounds short cycles, and the final bound follows from weak LP duality after deleting one vertex from each short cycle. There is no step in which a quantity is defined in terms of the claimed conclusion, no fitted parameter renamed as a prediction, and no uniqueness or ansatz imported from prior work. Section 4’s discussion of computational complexity barriers is explicitly heuristic, as the paper itself stresses, and is not used in the proofs of Theorems 1.3 or 1.4. The self-citations present are related-work pointers or credit for the algorithm and do not supply any unverified premise on which the central derivations depend.

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

The central claims rest on standard probabilistic and LP-duality tools plus the structural assumption of C4-freeness. There are no data-fitted parameters: α and \hat p are deterministic functions of d and ε chosen in the proof. No new entities are postulated; the fractional clique f is an explicit construction and U_{n,d} is a prior random graph model.

assumptions (7)
  • standard math Strong duality and weak duality of linear programming for the fractional chromatic/clique LP pair.
    Used in Theorem 1.4 proof to certify a lower bound via an explicit fractional clique; the paper invokes strong/weak duality in §1.3 and §3.
  • standard math Chernoff bound for sums of independent indicator variables.
    Used in the proof of Theorem 1.3 to show q runs of Algorithm 1 cover every vertex with high probability.
  • standard math Entropy bound binom(n,s) ≤ exp(n h(s/n)) with h defined in Lemma 3.2.
    Used in Lemma 3.2 first-moment estimate over independent sets of size s.
  • standard math Catalan recurrence identity used to bound the trace of A^r in Lemma 3.3.
    Used to sum the contributions of walks in the proof of Lemma 3.3.
  • standard math Lambert W function satisfies W(d)e^{W(d)}=d and W(d)=log d−log log d+o(1); harmonic numbers H_n = log n+O(1).
    Used throughout Theorem 1.4 and Section 1.2 to translate bounds into d/log d form.
  • domain assumption In the uniform attachment model U_{n,d}, for each i≤d, N_i^- = {0,...,i−1}, and for j>d, N_j^- is a uniformly random d-subset of earlier vertices; choices for distinct vertices are independent.
    This is the definitional structure of the random model (Definition 3.1), a modeling assumption rather than a theorem.
  • domain assumption C4-freeness implies |N_L(u)∩N_L(v)|≤1 for distinct left-neighbors, so η_{i,j,k}∈{0,1} in the supermartingale proof.
    This is the load-bearing structural property used in Lemma 2.2; the paper explicitly identifies it as the place where C4-freeness enters (§4).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sharp bounds for the fractional chromatic number of high-girth $d$-degenerate graphs." pith.science (2026). https://pith.science/paper/FWBGFFMQ

@misc{pith2026260726271,
  author       = {Pith},
  title        = {Pith review of: Sharp bounds for the fractional chromatic number of high-girth $d$-degenerate graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FWBGFFMQ}},
  note         = {Machine review of arXiv:2607.26271}
}
abstract

Martinsson and Steiner recently proved that the fractional chromatic number of any $d$-degenerate triangle-free graph $G$ satisfies $\chi_f(G) = O\left(\frac{d}{\log d}\right)$. They further conjectured a sharp leading constant $1 + o(1)$. In this paper, we confirm their upper bound conjecture for graphs having girth at least $5$. Our proof is constructive: it gives an efficient randomized algorithm that, with high probability, computes a fractional coloring of weight at most $(1 + o(1))\frac{d}{\log d}$ in such graphs. Furthermore, we establish their conjectured lower bound in a stronger form: for any constant $g \ge 4$, there exist $d$-degenerate graphs having girth at least $g$ with $\chi_f(G) \ge (1 - o(1))\frac{d}{\log d}$. This lower bound is achieved by analyzing a random graph based on the uniform attachment model. Notably, our results reveal that this model lacks the typical computational complexity barriers found in Erd\H{o}s-R\'enyi graphs, where there is a conjectured factor-$2$ algorithmic gap for this problem.

Figures

Figures reproduced from arXiv: 2607.26271 by the authors.

Figure 1
Figure 1. Possible configurations of C4 in G. We note that we may relax the C4-freeness condition further. Indeed, it suffices to insist that for every pair of vertices vi and vk, the set NR(vi)∩NL(vk) is sufficiently small (but possibly ≫ 1). More formally, if this set contained the ℓ vertices u1, . . . , uℓ we would need to know E   Y ℓ j=1 (1 + pi(uj ) [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 12 canonical work pages

  1. [1]

    On connectivity, conductance and bootstrap percolation for a random k-out, age-biased graph

    H. Acan and B. Pittel. “On connectivity, conductance and bootstrap percolation for a random k-out, age-biased graph”. In:Random Structures Algorithms56.1 (2020), pp. 37–62.doi:10.1002/ rsa.20872.url:https://doi.org/10.1002/rsa.20872(cit. on pp. 4, 8)

    work page doi:10.1002/rsa.20872(cit 2020

  2. [2]

    Coloring graphs with sparse neighborhoods

    N. Alon, M. Krivelevich, and B. Sudakov. “Coloring graphs with sparse neighborhoods”. In:J. Combin. Theory. B 77 (1999), pp. 73–82.doi:10.1006/jctb.1999.1910.url:https://doi.org/ 10.1006/jctb.1999.1910(cit. on p. 2)

    arXiv 1999

  3. [3]

    Coloring graphs with forbidden bipartite sub- graphs

    J. Anderson, A. Bernshteyn, and A. Dhawan. “Coloring graphs with forbidden bipartite sub- graphs”. In:Combinatorics, Probability and Computing32.1 (2023), pp. 45–67.doi:10 . 1017 / S0963548322000104.url:https://doi.org/10.1017/S0963548322000104(cit. on pp. 1, 16)

    work page doi:10.1017/s0963548322000104(cit 2023

  4. [4]

    The Johansson-Molloy theorem for DP-coloring

    A. Bernshteyn. “The Johansson-Molloy theorem for DP-coloring”. In:Random Structures & Algo- rithms54.4 (2019), pp. 653–664.doi:10.1002/rsa.20811.url:https://doi.org/10.1002/rsa. 20811(cit. on p. 1)

    work page doi:10.1002/rsa.20811.url:https://doi.org/10.1002/rsa 2019

  5. [5]

    Counting colorings of triangle-free graphs

    A. Bernshteyn, T. Brazelton, R. Cao, and A. Kang. “Counting colorings of triangle-free graphs”. In:Journal of Combinatorial Theory, Series B161 (2023), pp. 86–108.doi:10.1016/j.jctb. 2023.02.004.url:https://doi.org/10.1016/j.jctb.2023.02.004(cit. on p. 1)

    doi:10.1016/j.jctb 2023

  6. [6]

    Dynamic concentration of the triangle-free process

    T. Bohman and P. Keevash. “Dynamic concentration of the triangle-free process”. In:Random Structures Algorithms58.2 (2021), pp. 221–293.doi:10.1002/rsa.20973.url:https://doi. org/10.1002/rsa.20973(cit. on p. 1)

    work page doi:10.1002/rsa.20973.url:https://doi 2021

  7. [7]

    Bradaˇ c, J

    D. Bradaˇ c, J. Fox, R. Steiner, B. Sudakov, and S. Zhang.Coloring small locally sparse degenerate graphs and related problems. 2026. arXiv:2601.15245 [math.CO].url:https://arxiv.org/abs/ 2601.15245(cit. on p. 2)

    arXiv 2026

  8. [8]

    Bradshaw, A

    P. Bradshaw, A. Dhawan, A. Methuku, and M. C. Wigal.Toward Vu’s conjecture. 2025. arXiv: 2508.16818 [math.CO].url:https://arxiv.org/abs/2508.16818(cit. on p. 16)

    arXiv 2025

Show all 31 references
  1. [9]

    Campos, M

    M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe.A new lower bound for sphere packing

  2. [10]

    Graph structure via local occupancy

    E. Davies, R. J. Kang, F. Pirot, and J.-S. Sereni. “Graph structure via local occupancy”. 2020. arXiv:2003.14361 [math.CO].url:https://arxiv.org/abs/2003.14361(cit. on p. 1)

    2020 arXiv

  3. [11]

    Dhawan.Fractional coloring via entropy

    A. Dhawan.Fractional coloring via entropy. 2026. arXiv:2603 . 17730 [math.CO].url:https : //arxiv.org/abs/2603.17730(cit. on pp. 3, 15, 16)

    2026 arXiv

  4. [12]

    Dhawan, O

    A. Dhawan, O. Janzer, and A. Methuku.Independent sets and colorings ofK t,t,t-free graphs. 2025. arXiv:2511.17191 [math.CO].url:https://arxiv.org/abs/2511.17191(cit. on p. 1). 19

    2025

  5. [13]

    Separation choosability and dense bipartite induced subgraphs

    L. Esperet, R. J. Kang, and S. Thomass´ e. “Separation choosability and dense bipartite induced subgraphs”. In:Combinatorics, Probability and Computing28.5 (2019), pp. 720–732.doi:10 . 1017/S0963548319000026.url:https://doi.org/10.1017/S0963548319000026(cit. on p. 3)

    2019 doi

  6. [14]

    The triangle-free process and the Ramsey number R(3, k)

    G. Fiz Pontiveros, S. Griffiths, and R. Morris. “The triangle-free process and the Ramsey number R(3, k)”. In:Mem. Amer. Math. Soc.263.1274 (2020), pp. v+125.doi:10.1090/memo/1274.url: https://doi.org/10.1090/memo/1274(cit. on p. 1)

    2020 doi

  7. [15]

    Perfect matchings and Hamiltonian cycles in the preferential attachment model

    A. Frieze, X. P´ erez-Gim´ enez, P. Pra lat, and B. Reiniger. “Perfect matchings and Hamiltonian cycles in the preferential attachment model”. In:Random Structures Algorithms54.2 (2019), pp. 258–288. doi:10.1002/rsa.20778.url:https://doi.org/10.1002/rsa.20778(cit. on pp. 4, 8)

    2019 doi

  8. [16]

    On the independence and chromatic numbers of random regular graphs

    A. M. Frieze and T. Luczak. “On the independence and chromatic numbers of random regular graphs”. In:J. Combin. Theory Ser. B54.1 (1992), pp. 123–132.doi:10.1016/0095- 8956(92) 90070-E.url:https://doi.org/10.1016/0095-8956(92)90070-E(cit. on p. 1)

    1992 doi

  9. [17]

    Some results on chromatic number as a function of triangle count

    D. G. Harris. “Some results on chromatic number as a function of triangle count”. In:SIAM Journal on Discrete Mathematics33.1 (2019), pp. 546–563.doi:10.1137/17M115918X.url:https: //doi.org/10.1137/17M115918X(cit. on p. 2)

    2019 doi

  10. [18]

    Hefty, P

    Z. Hefty, P. Horn, D. King, and F. Pfender.ImprovingR(3, k)in just two bites. 2026. arXiv: 2510.19718 [math.CO].url:https://arxiv.org/abs/2510.19718(cit. on p. 2)

    2026

  11. [19]

    Uniformly random colourings of sparse graphs

    E. Hurley and F. Pirot. “Uniformly random colourings of sparse graphs”. In:Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023, pp. 1357–1370.doi:10.1145/3564246. 3585242.url:https://doi.org/10.1145/3564246.3585242(cit. on p. 1)

    2023

  12. [20]

    Johansson.Asymptotic choice number for triangle free graphs

    A. Johansson.Asymptotic choice number for triangle free graphs. Technical Report 91–95. DIMACS, 1996 (cit. on p. 1)

    1996

  13. [21]

    R. M. Karp.The Probabilistic Analysis of some Combinational Search Algorithms. Tech. rep. UCB/ERL M581. Apr. 1976.url:http://www2.eecs.berkeley.edu/Pubs/TechRpts/1976/ 28848.html(cit. on p. 1)

    1976

  14. [22]

    On Brooks’ theorem for sparse graphs

    J. H. Kim. “On Brooks’ theorem for sparse graphs”. In:Combin. Probab. Comput.4.2 (1995), pp. 97– 132.doi:10.1017/S0963548300001528.url:https://doi.org/10.1017/S0963548300001528 (cit. on p. 15)

    1995 doi

  15. [23]

    γ-variable first-order logic of uniform attachment random graphs

    Y. A. Malyshkin and M. E. Zhukovskii. “γ-variable first-order logic of uniform attachment random graphs”. In:Discrete Math.345.5 (2022), Paper No. 112802, 12.doi:10 . 1016 / j . disc . 2022 . 112802.url:https://doi.org/10.1016/j.disc.2022.112802(cit. on pp. 4, 8)

    2022

  16. [24]

    Random independent sets in triangle-free graphs

    A. Martinsson and R. Steiner. “Random independent sets in triangle-free graphs”. In:Forum Math. Sigma13 (2025), Paper No. e156, 19.doi:10.1017/fms.2025.10112.url:https://doi.org/ 10.1017/fms.2025.10112(cit. on pp. 2, 3, 15)

    2025

  17. [25]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal.Probability and computing. Second. Randomization and proba- bilistic techniques in algorithms and data analysis. Cambridge University Press, Cambridge, 2017, pp. xx+467.isbn: 978-1-107-15488-9 (cit. on p. 6)

    2017

  18. [26]

    The list chromatic number of graphs with small clique number

    M. Molloy. “The list chromatic number of graphs with small clique number”. In:J. Combin. Theory. B 134 (2019), pp. 264–284.doi:10.1016/j.jctb.2018.06.007.url:https://doi.org/10. 1016/j.jctb.2018.06.007(cit. on p. 1)

    2019 doi

  19. [27]

    Molloy and B

    M. Molloy and B. Reed.Graph Colouring and the Probabilistic Method. Vol. 23. Algorithms and Combinatorics. Springer-Verlag, Berlin, 2002, pp. xiv+326.isbn: 3-540-42139-4.doi:10.1007/978- 3-642-04016-0.url:https://doi.org/10.1007/978-3-642-04016-0(cit. on p. 5)

    2002 doi

  20. [28]

    The spectral density of Hardy kernel matrices

    A. Pushnitski. “The spectral density of Hardy kernel matrices”. In:J. Operator Theory89.1 (2023), pp. 3–21 (cit. on pp. 15, 18)

    2023

  21. [29]

    A note on the independence number of triangle-free graphs

    J. B. Shearer. “A note on the independence number of triangle-free graphs”. In:Discrete Mathe- matics46.1 (1983), pp. 83–87.doi:10.1016/0012-365X(83)90273-X.url:https://doi.org/ 10.1016/0012-365X(83)90273-X(cit. on p. 1). 20

    1983 doi

  22. [30]

    R. P. Stanley.Catalan numbers. Cambridge University Press, New York, 2015.doi:10 . 1017 / CBO9781139871495.url:https://doi.org/10.1017/CBO9781139871495(cit. on p. 14)

    2015 doi

  23. [2023]

    arXiv:2312.10026 [math.MG].url:https://arxiv.org/abs/2312.10026(cit. on pp. 1, 16)

    arXiv

Pith tools

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