Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

The asymptotic $\chi$-boundedness of hereditary families

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that almost every graph avoiding a fixed tree or a cycle other than C6 has χ(G)=ω(G), and gives the first asymptotic χ-boundedness bound for C6-free graphs.

desk verdict The framework is real and clean, but the headline theorems are only as solid as two unpublished companion papers and an unreferenced C6 assertion. read the letter →

arxiv 2506.01070 v1 pith:HY36CBE6 submitted 2025-06-01 math.CO

Bruce Reed , Yelena Yuditsky This is my paper
classification math.CO MSC 05C1505C80
keywords asymptoticchi-boundednesshereditaryfamiliesH-freegraphschromaticnumbercliquewitnessingpartitionsC6-free
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 studies hereditary families of graphs and asks what happens to the chromatic number of a typical member relative to its clique number. It proves two asymptotic statements: for every fixed tree T, almost all T-free graphs satisfy χ(G)=ω(G), and for every fixed cycle C_k with k≠6, almost all C_k-free graphs satisfy χ(G)=ω(G). The sole exception is C6, for which the paper establishes the first asymptotic χ-boundedness result with f(w)=(1+o(1))$w^{2}$/log w. These results say that typical members of these families are asymptotically perfect: their chromatic number equals their clique number, and the C5 case is shown to be genuinely perfect via the Strong Perfect Graph Theorem. The proof strategy turns typical structure into colourings through witnessing partitions and a probabilistic extension lemma.

What carries the argument

The central objects are witnessing partitions and the witnessing partition number wpn(H): the largest t such that H cannot be partitioned into s stable sets and c cliques with s+c=t. A witnessing partition of H-freeness for G is a partition of V(G) into that many parts such that no way of partitioning H into s stable sets and c cliques is induced inside the parts. The conversion from partition to colouring is carried by the concept of a (b,f)-nicely partitionable hereditary family, meaning one in which almost every member admits one of finitely many certified patterns on a nearly equal partition, with each part either f(ω)-colourable using colour classes of size at most b or a clique, together with Corollary 12, which says such families are asymptotically f(ω)-colourable. The probabilistic heart is Theorem 11, which shows that given a partition with each part coloured in f(ω) colours using colour classes of bounded size, almost every extension of the pattern is f(ω)-colourable with slightly larger colour classes; its proof uses the standard matching condition for bipartite graphs and standard tail bounds for sums of independent Bernoulli variables.

What would settle it

Exhibit a fixed tree T (or a fixed cycle C_k with k≠6) and infinitely many n for which a non-negligible fraction of all T-free (or C_k-free) graphs on n vertices has χ(G)>ω(G), or, for C6, a non-negligible fraction of C6-free graphs on n vertices with χ(G) exceeding (1+o(1))ω(G)^2/log ω(G) or a violation of the asserted stable-set-complement-of-girth-five partition.

Watch

Extended reading notes

Core claim

The central claim is that forbidding a fixed tree or a fixed cycle other than C6 pushes almost every graph in the family to the absolute minimum possible chromatic number: χ(G)=ω(G). The paper proves this not by bounding all H-free graphs but by describing the typical structure of almost all of them. For every such H, almost every H-free graph admits a nontrivial witnessing partition into a bounded number of parts, each of which induces a very restricted graph class (cliques, complements of matchings, graphs whose complements have only star or triangle components, and so on). The paper then proves a probabilistic lemma: if each part of such a partition has been coloured with the right number of colours using bounded colour-class sizes, then almost every way of adding the cross-part edges preserves that colouring. Applied to the witnessing partitions, this yields almost sure χ=ω. For C6 the partition is different, since almost every C6-free graph splits into a stable set and the complement of a graph of girth five, and a known bound on the clique number of such complements converts this into the stated f(w).

Load-bearing premise

The load-bearing premise is that the structural classifications of almost all T-free and C_k-free graphs quoted from two companion papers still listed as to be submitted, together with the unreferenced assertion that almost every C6-free graph can be partitioned into a stable set and the complement of a girth-five graph, are all correct; if any of these fails, the corresponding theorem does not follow.

Editorial extensions

If this is right

  • For every fixed tree T, almost every T-free graph can be coloured with exactly ω(G) colours, so the typical member of every tree-forbidding hereditary class satisfies the minimal possible colouring bound.
  • For every fixed cycle C_k with k≠6, almost every C_k-free graph satisfies χ(G)=ω(G), extending the previously known C4 and C5 cases to all other cycles and leaving C6 as the only cycle whose asymptotic behaviour is genuinely different.
  • The C6-free graphs are asymptotically χ-bounded with f(w)=(1+o(1))w^2/log w; the paper observes that improving this would require proving that complements of girth-five graphs typically have clique number of order sqrt(n log n).
  • The same partition-to-colouring framework yields that almost every string graph satisfies χ(G)=ω(G).
  • For every graph H that is critical in the sense that almost all H-free graphs are partitionable into s stable sets and c cliques for some fixed pair (s,c), almost every H-free graph satisfies χ(G)=ω(G).

Reading between the lines

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

  • An asymptotic version of the classical conjecture for all forests would not follow from Theorem 2 by a simple subset argument: the 'almost all' quantifier does not automatically transfer from the larger tree-free family to the smaller forest-free subfamily, so a separate structural analysis of typical forest-free graphs would be needed.
  • The C6 analysis identifies a concrete bottleneck for improving Theorem 4: if the typical clique number of an n-vertex complement of a girth-five graph is asymptotically sqrt(n log n), then the squared bound is essentially forced, so measuring this quantity directly would determine whether the bound is tight.
  • The probabilistic extension lemma (Theorem 11) is a reusable black box: any hereditary family whose almost-all members can be certified by witnessing partitions with bounded-colour-class colourings will inherit an asymptotic χ-boundedness bound, as the string-graph corollary already demonstrates.
  • The main theorems are conditional on unpublished structural classifications; completing those classifications is the natural next step, and the same partitions should also yield enumeration results for tree-free and cycle-free graphs.
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

4 major / 5 minor

Summary. The paper introduces the notion of asymptotic χ-boundedness for hereditary families and states three main results: Theorem 2 says that for every tree T, almost all T-free graphs satisfy χ(G)=ω(G); Theorem 3 says the same for every cycle C_k with k≠6; Theorem 4 says the C_6-free graphs are asymptotically χ-bounded with bounding function f(w)=(1+o(1))w^2/log w. The method is a framework based on witnessing partitions and (µ,l)-partitionable hereditary families: Theorem 11 and Corollary 12 convert 'nicely partitionable' families into families in which almost all members are f(ω)-colourable. Theorem 10 is then presented as supplying the needed partitionability for trees and cycles, and Theorem 9 supplies the C_6 partition. The proofs of Theorems 2 and 3 are meant to follow from Theorem 10 plus Corollary 12; Theorem 4 follows from Theorem 9 plus Observation 8 and Shearer's bound.

Significance. If fully established, Theorems 2 and 3 are striking: they assert that almost all graphs avoiding a fixed tree or a non-6 cycle are perfect, which is far stronger than asymptotic χ-boundedness. Theorem 4 would give the first asymptotic χ-boundedness result for C_6-free graphs with an explicit bound of order w^2/log w. The framework of Theorem 11 and Corollary 12 is original, self-contained in outline, and potentially reusable; Corollary 17 for string graphs is a nice additional application. The principal weakness is that the load-bearing structural inputs are not contained in this manuscript: the proof of Theorem 10 is a sequence of citations to the unpublished manuscripts [24] and [23], and Theorem 9 is asserted without proof or reference. As submitted, the central theorems cannot be independently verified.

major comments (4)
  1. [§4, Proof of Theorem 10] The proof of Theorem 10 quotes seven structural classification theorems from the unpublished manuscript [24] (Theorems 2.21, 2.22, 2.28, 2.33, 2.35, 2.37, 2.39) and analogous cycle classifications from the unpublished [23]. Since Theorem 10 is the entire structural input for Theorems 2 and 3, both main theorems are conditional on two manuscripts that are not available to the reader. The authors should either reproduce the statements (and proofs or precise public references) of these classifications, or clearly mark Theorems 2 and 3 as conditional on forthcoming work.
  2. [§4, Lemma 13] Lemma 13 is cited from [24] and is used in the proof of Theorem 10 to pass from the quoted structural partition results to the counting condition (b) in the definition of (µ,l)-partitionability. This is a second load-bearing dependence on [24], and the lemma is not stated in sufficient detail for the reader to verify the Θ(1) count. The dependence should be removed or the lemma proved in the manuscript.
  3. [§3, Theorem 9 (RS)] Theorem 9, which asserts that almost every C_6-free graph can be partitioned into a stable set and the complement of a graph of girth five, is stated with the label '(RS)' but is given neither a proof nor a reference. Theorem 4 and the remark following it rest entirely on this statement together with Shearer's bound. As submitted, the C_6 result is unsupported.
  4. [§5, Proof of Theorem 11] The case split in the proof of the two-part case is not justified. The sentence 'this lower bound on the degree also implies c−|S| ≥ c/(2b^2+1)' does not follow from the assumption that all vertices have degree greater than c/(2b^2+1); a Hall-violating set S can be large while |N(S)| is much smaller than |S|. The proof should be rewritten, for example by taking a minimal Hall violator and carefully relating the size of S to the degree condition, or by using a different concentration argument.
minor comments (5)
  1. [§1, Corollary 6] The proof of Corollary 6 contains duplicated and garbled sentences: the two sentences beginning 'When we delete a stable set from C_{2k+1}' and 'When we delete a clique from C_{2k+1}' are repeated with the clauses swapped. The argument should be rewritten for clarity.
  2. [§3, after Theorem 9] The phrase 'E_3-free' should be 'triangle-free' or defined explicitly; Shearer's theorem [29] is about the independence number of triangle-free graphs, and the notation E_3 is otherwise unused.
  3. [§4, Proof of Theorem 10] The phrase 'an 1/9 -eqi-partition' is ungrammatical, and expressions such as 'partitioned into wpn(H)=α(T)−1 cliques' should be rephrased as 'partitioned into wpn(H)=α(T)−1 parts, each of which is a clique' or similar.
  4. [§5, Proof of Theorem 11] The proof refers to 'c0−1 variables' without defining c0; this should be 'c−1' or a defined symbol such as c_b.
  5. [§5, Theorem 11] The failure probability in Theorem 11 is written o_c(1); since c is the number of colours and may depend on n, the asymptotic should be clarified, for example as uniform in n over the range of c considered in Corollary 12.

Circularity Check

4 steps flagged · score 7.0 of 10

Central theorems reduce to structural classifications in unpublished same-author companion papers [23,24]; Theorem 9 (RS) for C6-free graphs is asserted without proof or reference.

  1. self citation load bearing [Section 4, Proof of Theorem 10 (items 1–7, citing [24])]
    "The following results are proven there: 1. If T has no perfect matching and is not a subdivided star, then almost every T-free graph can be partitioned into wpn(H)=α(T)−1 cliques ([24], Theorem 2.21), 2. If T is a subdivided star, ... ([24], Theorem 2.22), ... 7. If T is P6 then wpn(H)=2 and almost every T-free graph can be partitioned into a clique and a set inducing a graph whose complement only contains components which are obtained from a clique and a stable set by adding all edges between them ([24], Theorem 2.39)."

    Theorem 10 is the structural input from which Theorems 2 and 3 are derived via Corollary 12. Its proof consists of a list of seven classification theorems quoted from Reed and Yuditsky [24], which the bibliography lists as 'To be submitted' and which has the same two authors as the present paper. The manuscript states no statement or proof of these theorems, so the main tree-result is not derived here at all; it is imported from an unpublished companion paper by the same authors. This is a load-bearing self-citation chain: if the classification is false or incomplete, Theorems 2 and 3 do not follow, and no independent check is available in this paper.

  2. self citation load bearing [Section 4, Proof of Theorem 10 (even cycles, citing [23])]
    "Reed [23] has shown that (i) for k even and at least 12, almost every C_k free graph has a partition into wpn(C_k)−1 = (k−4)/2 cliques and a set inducing a graph whose complements only has stars and triangles as components ... and (iii) almost every C_8 free graph has a partition into 2 cliques and a set inducing a graph whose complements are formed from a clique and a stable set by adding all edges between them."

    The even-cycle half of Theorem 3 (k even, k≠6) is obtained by importing classifications from Reed [23], a single-author companion paper by one of the present authors listed as 'To be submitted'. The proof of Theorem 10 for cycles has no other content; it says 'The same argument as above shows...' and then applies Corollary 12. Thus the cycle theorem is conditional on an unpublished self-citation: the claimed asymptotic chi-boundedness is not demonstrated in this paper, but deferred to a companion manuscript by the same author.

2 more flagged steps
  1. other [Section 3, Theorem 9 (used in proof of Theorem 4)]
    "Theorem 9 (RS). Almost every C6-free graph can be partitioned into a stable set and the complement of a graph of girth five."

    This is the sole structural input for Theorem 4. It is asserted with the marker '(RS)' and no proof or reference; the bibliography contains no RS entry. The derivation of the bound f(w)=(1+o(1))w^2/log w is then just: apply Shearer's bound to the complement of a girth-five graph plus one colour for the stable set. Since the existence of the partition is never established, Theorem 4 is unsupported as submitted. This is not a pure self-citation circularity, but it is a load-bearing missing input in the derivation chain and must be weighed in the verdict.

  2. self citation load bearing [Section 4 (Lemma 13, cited from [24])]
    "Lemma 13. ([24], Lemma 2.20) Let p≥1 be fixed, and suppose that F_1, ..., F_p are families containing subgraphs of every size and for sufficiently large l_0, we have ..."

    The counting step that turns the seven classification theorems into the (1/9,2)-partitionability statement uses Lemma 13 from [24], again an unpublished companion paper by the same authors. This lemma is load-bearing for the conclusion that the partitions cover almost all T-free graphs, so the self-citation chain is needed in more than one place. The paper's own framework (Theorem 11 and Corollary 12) is proven in-paper, but it cannot supply the missing structural classification.

full rationale

The paper's own combinatorial machinery — Theorem 11 (colouring random extensions of patterns) and Corollary 12 — is self-contained and appears to be genuine, independent content. However, the main theorems 2 and 3 are not established within the paper: the proof of Theorem 10 delegates the entire structural classification of almost all T-free graphs to seven theorems in Reed and Yuditsky [24] and the cycle classifications to Reed [23], both listed as 'To be submitted' and both authored by the present authors. No statements of these theorems are included, so the reader cannot verify the input. This is a load-bearing self-citation chain rather than a construction-equivalence circularity: the derived claim is not identical to an input by definition, but the derivation is conditional on unpublished claims made by the same authors. Theorem 9 (RS) for C6-free graphs is even weaker: it is asserted with no reference at all, making Theorem 4's bound rest on an unsupported structural assertion. Weighting the absence of any independent check of the companion papers, and the fact that the paper's own framework is sound, gives a score of 7 rather than 8 or 9: the reduction is to unverified self-citations, not to a parameter that is fitted by construction, but the central results are not self-contained as submitted.

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

The paper's main theorems are derived from a framework (Corollary 12) whose inputs are structural classification theorems, most of which are either from unpublished companion papers by the same authors or an unreferenced assertion. The reader is asked to accept these inputs without access to the proofs; they are the true axioms of the paper.

assumptions (8)
  • standard math Strong Perfect Graph Theorem [7]: a graph is perfect iff it contains no induced odd cycle of length at least 5 or its complement.
    Used in Corollary 6 and to connect chi=omega to the absence of odd holes; proven in [7].
  • ad hoc to paper Structural classification of typical T-free graphs (Theorems 2.21, 2.22, 2.28, 2.33, 2.35, 2.37, 2.39 of [24]).
    These are load-bearing inputs for Theorem 10; they are stated to be proven in an unpublished companion paper by the same authors and are not reproduced here.
  • domain assumption Balogh-Butterfield structural results for odd cycles C_k, k at least 7 [1].
    Published results used in Theorem 10 to certify (2,f)-nice partitionability for odd cycles.
  • ad hoc to paper Reed's structural results for even cycles C_k, k at least 8 [23].
    Cited as 'to be submitted'; the same-argument assertion in Section 4 depends on it.
  • ad hoc to paper Theorem 9 (RS): almost every C6-free graph can be partitioned into a stable set and the complement of a graph of girth five.
    Asserted in Section 3 with no bibliographic reference; the reference list has no RS entry, so this cannot be checked.
  • standard math Shearer's bound [29]: every triangle-free graph on l vertices has independence number (1+o(1))sqrt(l log l).
    Used in the proof of Theorem 4 to bound the clique number of the complement of a girth-five graph.
  • standard math Counting of P4-free graphs via Seinsche's theorem [28].
    Used to bound the number of patterns in Theorem 10.
  • standard math Hall's theorem and Chernoff bounds.
    Used in the proof of Theorem 11.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The asymptotic $\chi$-boundedness of hereditary families." pith.science (2026). https://pith.science/paper/HY36CBE6

@misc{pith2026250601070,
  author       = {Pith},
  title        = {Pith review of: The asymptotic $\chi$-boundedness of hereditary families},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HY36CBE6}},
  note         = {Machine review of arXiv:2506.01070}
}
abstract

A family ${\cal F}$ of graphs is asymptotically $\chi$-bounded with bounding function $f$ if almost every graph $G$ in the family satisfies $\chi(G) \le f(\omega(G))$. A graph is $H$-free if it does not contain $H$ as an induced subgraph. We ask which hereditary families are asymptotically $\chi$-bounded, and discuss some related questions. We show that for every tree $T$, almost all $T$-free graphs $G$ satisfy $\chi(G)=\omega(G)$. We show that for every cycle $C_k$ except $C_6$, almost every $C_k$-free graph $G$ satisfies $\chi(G) = \omega(G)$. We show that the $C_6$-free graphs are asymptotically $\chi$-bounded with bounding function $f(w)=(1+o(1))\frac{w^2}{\log w}$.

Discussion (0). Sign in 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

  1. Cops and Robbers, Clique Covers, and Induced Cycles

    math.CO 2025-07 conditional novelty 7.0 of 10

    For every k there is a graph whose cop number, independence number, and clique-cover number are all equal to k, and any graph with these equal for k≥3 contains induced cycles of every length from 3 to k+1.

Reference graph

Works this paper leans on

32 extracted references · 27 canonical work pages · cited by 1 Pith paper

  1. [24]

    Reed and Y

    B. Reed and Y. Yuditsky. The structure of a typicalT-free graph. To be submitted

    work page

  2. [23]

    B. Reed. The global structure of a typical graph withoutHas an induced subgraph when His a cycle. To be submitted

    work page

  3. [1]

    Balogh and J

    J. Balogh and J. Butterfield. Excluding induced subgraphs: Critical graphs. Random Structures and Algorithms, 38(1-2): 100-120 (2011)

    2011

  4. [2]

    C. Berge. Perfect graphs. Six Papers on Graph Theory. Calcutta: Indian Statistical Institute: 1-21 (1963)

    work page 1963

  5. [3]

    Bollob´ as and A

    B. Bollob´ as and A. Thomason, Hereditary and monotone properties of graphs. The mathematics of Paul Erd˝ os II 14: 70-78 (1997)

    work page 1997

  6. [4]

    Bondy and U.S.R Murty

    J.-A. Bondy and U.S.R Murty. Graph theory. Graduate texts in mathematics, Springer, (2007)

    2007

  7. [5]

    Chernoff

    H. Chernoff. A note on an inequality involving the normal distribution. Ann. Probab., 9: 533-535 (1981)

    1981

  8. [6]

    Chudnovsky, A

    M. Chudnovsky, A. Scott and P. Seymour. Induced subgraphs of graphs with large chro- matic number. XII. Two-legged caterpillars.https://web.math.princeton.edu/ ~pds/ papers/cuttingedge/paper.pdf

    work page

Show all 32 references
  1. [7]

    Chudnovsky, N

    M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas. The strong perfect graph theorem. Annals of Mathematics, 164(1): 51-229 (2006)

    2006

  2. [8]

    Chudnovsky, A

    M. Chudnovsky, A. Scott and P. Seymour. Induced subgraphs of graphs with large chro- matic number. XII. Distant stars. J. Graph Theory 92:237–254 (2019)

    2019

  3. [9]

    Gy´ arf´ as

    A. Gy´ arf´ as. Problems from the world surrounding perfect graphs. Zastosow Ania Matem- atyki, Applicationes Mathematicae, XIX, 3-4: 413-441 (1987)

    1987

  4. [10]

    P. Erd˝ os. Graph theory and probability. Canad. J. Math. 11: 34-38 (1959)

    1959

  5. [11]

    Erd˝ os, D

    P. Erd˝ os, D. J. Kleitman and B. L. Rothschild. Asymptotic enumeration ofKn-free graphs. International Colloquium on Combinatorial Theory, Atti dei Convegni Lincei 17(2): 19-27 (1976). 13

    1976

  6. [12]

    R. Kang, C. McDiarmid, B. Reed and A. Scott. For most graphsH, mostH-free graphs have a linear homogeneous set. Random Structures and Algorithms 45(3): 343-361 (2014)

    2014

  7. [13]

    H. A. Kierstead and S. G. Penrice. Radius two trees specifyχ-bounded classes. Journal of Graph Theory 18(2): 119-129 (1994)

    1994

  8. [14]

    H. A. Kierstead and Y. Zhu. Radius three trees in graphs with large chromatic number. SIAM J. Discrete Math. 17(4): 571-581 (2004)

    2004

  9. [15]

    J. Kim, D. K¨ uhn, D. Osthus, T. Townsend. Forbidding induced even cycles in a graph: typical structure and counting.http://arxiv.org/abs/1507.04944

    arXiv

  10. [16]

    Kolaitis, H.J

    Ph.G. Kolaitis, H.J. Pr¨ omel and B.L. Rothschild.K ℓ+1-free graphs: asymptotic structure and a 0 - 1 law. Trans. Amer. Math. Soc. 303: 637-671 (1987)

    1987

  11. [17]

    Norin, Y

    S. Norin, Y. Yuditsky. Typical Structure of Hereditary Graph Families. II. Exotic Exam- ples. Random Structures & Algorithms 66(1): e21272 (2025)

    2025

  12. [18]

    J. Pach, B. Reed and Y. Yuditsky. Almost all String Graphs are Intersection Graphs of Plane Convex Sets. Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018)

    2018

  13. [19]

    H. J. Pr¨ omel and A. Steger. Excluding induced subgraphs: Quadrilaterals. Random Structures and Algorithms 2: 55-71 (1991)

    1991

  14. [20]

    H. J. Pr¨ omel and A. Steger. Excluding induced subgraphs III: A general asymptotic. Random Structures and Algorithms 3(1): 19-31 (1992)

    1992

  15. [21]

    H. J. Pr¨ omel and A. Steger. Excluding induced subgraphs II: Extremal graphs. Discrete Applied Mathematics 44(1-3): 283-294 (1993)

    1993

  16. [22]

    H. J. Pr¨ omel and A. Steger. Almost all Berge graphs are perfect. Combinatorics, Proba- bility and Computing 1: 53-79 (1992)

    1992

  17. [25]

    A. D. Scott. Induced trees in graphs of large chromatic number. J. Graph Theory 24: 297-311 (1997). 14

    1997

  18. [26]

    Scott and P

    A. Scott and P. Seymour. Induced subgraphs of graphs with large chromatic number. XIII. New brooms. European J. of Combinatorics 84:103024 (2020)

    2020

  19. [27]

    Scott and P

    A. Scott and P. Seymour. A survey ofχ-boundedness. Journal of Graph Theory. 95(3):473- 504 (2020)

    2020

  20. [28]

    Seinsche

    D. Seinsche. On a property of the class ofn-colorable graphs. J. Combin. Theory Ser. B 16: 191-193 (1974)

    1974

  21. [29]

    J. Shearer. A note on the independence number of triangle-free graphs. Discrete Mathe- matics 46: 83-87 (1983)

    1983

  22. [30]

    S. Spirkl. Cliques, Stable Sets, and Coloring in Graphs with Forbidden Induced Subgraphs. Ph.D. thesis, Princeton University (2018)

    2018

  23. [31]

    D.P. Sumner. Subtrees of a graph and chromatic number. The Theory and Applications of Graphs, John Wiley & Sons, New York: 557-576 (1981)

    1981

  24. [32]

    A. A. Zykov. On some properties of linear complexes. Mat. Sb. (N.S.), 24(66)(2):163-188 (1949). in Russian. 15

    1949

Pith tools

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