Pith. sign in

REVIEW 2 minor 1 cited by

Graphs with no induced E-graph or Bird satisfy the Erdős-Hajnal conjecture.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

Proves Erdős-Hajnal conjecture for E-graph and Bird forbidden induced subgraphs via generalized iterative sparsification and reductions to generalized nice and (*) properties.

T0 review reviewed 2026-06-28 challenge →

load-bearing objection This extends EH to the E-graph and Bird by generalizing the nice property in the Nguyen-Scott-Seymour sparsification framework.

arxiv 2606.06258 v2 pith:NATY5ARQ submitted 2026-06-04 math.CO

ErdH{o}s-Hajnal beyond the five-vertex path

Shenwei Huang , Yiao Ju , Yidong Zhou This is my paper
classification math.CO
keywords Erdős-Hajnal conjectureinduced subgraphE-graphBird graphforbidden induced subgraphgraph Ramsey theorysparsification
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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 shows that the Erdős-Hajnal conjecture holds when the forbidden induced subgraph is either the E-graph or the Bird graph. The E-graph is formed by attaching a pendant edge to the middle vertex of a five-vertex path; the Bird is formed by attaching a pendant edge to one horn of a bull. This extends known cases for the plain five-vertex path and the bull. The argument reduces the conjecture, subject to a technical condition, to a generalized nice property, verifies the condition using Ramsey theory together with a new embedding method for leaf-free graphs, then reduces further to a property (*) that both graphs satisfy. One auxiliary step establishes the conjecture for certain auxiliary graphs by defining suitable equivalence relations.

Core claim

For the E-graph and the Bird graph, every n-vertex graph containing neither as an induced subgraph has a clique or independent set of size at least n^c for some positive c that depends only on the forbidden graph. The proof generalizes the iterative sparsification framework by first reducing (under a technical condition) the conjecture to the generalized nice property, confirming that E-graph and Bird meet the condition, then reducing the generalized nice property to a new property (*) and verifying that both graphs satisfy (*).

What carries the argument

The generalized nice property, which extends the nice property from earlier work on the five-vertex path and serves as the intermediate target in the reduction of the Erdős-Hajnal conjecture.

Load-bearing premise

That the E-graph and Bird meet the technical condition allowing reduction of the conjecture to the generalized nice property.

What would settle it

A sequence of n-vertex graphs with neither an induced E-graph nor an induced Bird whose largest clique and largest independent set are both smaller than n to any fixed positive power.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • The conjecture holds for all graphs forbidding the E-graph as an induced subgraph.
  • The conjecture holds for all graphs forbidding the Bird as an induced subgraph.
  • The iterative sparsification method extends from the five-vertex path to these two larger graphs.
  • Certain auxiliary graphs constructed during the proof also obey the Erdős-Hajnal conjecture.
  • The new embedding technique for graphs without leaves can be reused for other forbidden subgraphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction chain might apply to other graphs obtained by adding pendant edges to paths or bulls.
  • If the generalized nice property can be shown for additional graphs, the conjecture would hold for those graphs as well.
  • The equivalence-relation technique for auxiliary graphs may simplify proofs for other small forbidden induced subgraphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper claims to prove the Erdős-Hajnal conjecture for graphs with no induced E-graph (five-vertex path plus a pendant edge on the middle vertex) and no induced Bird graph (bull plus a pendant edge on one horn). It generalizes the iterative sparsification framework of Nguyen-Scott-Seymour by reducing (up to a technical condition) to a generalized nice property, verified for the target graphs via the Ramsey theorem and a new embedding for leaf-free graphs; it then reduces the generalized nice property to property (*) and verifies the latter for E-graph and Bird via equivalence relations on auxiliary graphs.

Significance. If correct, the result adds two new forbidden induced subgraphs to the list of cases where the Erdős-Hajnal conjecture is known to hold, directly extending the five-vertex path result of Nguyen-Scott-Seymour and the bull result of Chudnovsky-Safra. The generalization of the nice property and the embedding technique for graphs without leaves are methodological contributions that may apply more broadly. The argument follows the established framework without introducing free parameters or ad-hoc axioms.

minor comments (2)
  1. [Abstract] Abstract: correct the typographical errors 'generlaized' (should be 'generalized'), 'ues' (should be 'use'), and 'satisfiy' (should be 'satisfy').
  2. [Abstract] Abstract (proof outline paragraph): the reduction steps and verification of the technical condition are described at a high level; add explicit cross-references to the sections or lemmas where each step (including the Ramsey application and the leaf-free embedding) is carried out.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of the results, and recommendation of minor revision. No major comments are listed in the report, so we have no specific points requiring point-by-point rebuttal or revision at this stage. We will incorporate any minor editorial suggestions during the revision process.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation follows the established iterative sparsification framework of Nguyen-Scott-Seymour (distinct prior authors) but introduces independent reductions: a generalized nice property, a new embedding technique for leaf-free graphs, and verification of property (*) for the E-graph and Bird via equivalence relations on auxiliary graphs. These steps are not reductions by construction to the paper's own inputs or self-citations; the cited framework is external and the new technical conditions are addressed via Ramsey theory and original arguments. No self-definitional, fitted-prediction, or load-bearing self-citation patterns appear. The central claims rest on content independent of the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof invokes the Ramsey theorem as background and the prior iterative sparsification framework; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Ramsey Theorem
    Used to prove that E-graph and Bird satisfy the technical condition (abstract).

reviewed 2026-06-28 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Erd\H{o}s-Hajnal beyond the five-vertex path." pith.science (2026). https://pith.science/paper/NATY5ARQ

@misc{pith2026260606258,
  author       = {Pith},
  title        = {Pith review of: Erd\Hos-Hajnal beyond the five-vertex path},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NATY5ARQ}},
  note         = {Machine review of arXiv:2606.06258}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The well-known Erd\H{o}s-Hajnal conjecture states that for any graph $H$, there is a constant $c=c(H)>0$ such that every $n$-vertex graph $G$ with no induced copies of $H$ contains a clique or an independent set of size at least $n^{c}$. We prove that Erd\H{o}s-Hajnal conjecture holds for two more graph classes-graphs with no induced copies of $E$-graph and graphs with no induced copies of Birds, where $E$-graph is the graph obtained from the five-vertex path by adding a pendent edge to the middle vertex of the path and Bird is the graph obtained from a bull by adding a pendent edge to one horn of the bull. Our results generalize the result of Nguyen, Scott and Seymour on the five-vertex path (Proceedings of London Mathematical Society 2026) and the result of Chudnovsky and Safra on the bull graph (Journal of Combinatorial Theory Series B 2008). The proof uses the iterative sparsification framework proposed by Nguyen, Scott and Seymour with our generalization. We first reduce, up to some technical condition, Erd\H{o}s-Hajnal conjecture to a property called generlaized nice, which is a generalization of the ``nice'' property used in [T.~Nguyen, A.~Scott, and P.~Seymour. Induced subgraph density. VII. The five-vertex path. {\em Proceedings of the London Mathematical Society}, 132(3):e70133, 2026]. We ues Ramsey Theorem and a new idea for embedding graphs with no leaf vertices to prove that $E$-graph and Bird satisfy this technical condition. We then reduce the generalized nice property to a new property $(*)$. Finally, we show that $E$-graph and Bird graph satisfiy $(*)$. One key step in the proof is to prove, via defining appropriate equivalence relations, that certain auxiliary graph satisfies the Erd\H{o}s-Hajnal conjecture.

Figures

Figures reproduced from arXiv: 2606.06258 by Shenwei Huang, Yiao Ju, Yidong Zhou.

Figure 1
Figure 1. Figure 1: The bull graph. One can easily show via Theorem 1.4 that every graph with at most four vertices satisfies the Erd˝os-Hajnal property. There are four prime 5-vertex graphs: the bull (see [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Two prime 6-vertex graphs that have the Erd˝os-Hajnal property. 1.3 Erd˝os-Hajnal for two graphs In the following we mention some results on Erd˝os-Hajnal property of graphs with more than one forbidden induced subgraph. Bousquet, Lagoutte and Thomass´e [3] proved that for every integer k ≥ 1, {Pk, Pk} has the Erd˝os-Hajnal property. A stronger result that if H1, H2 are forests, then {H1, H2} has the Erd˝o… view at source ↗
Figure 3
Figure 3. Figure 3: for an example). They proved the following theorem. P4 star-expansion of P4 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The graphs E-graph and its complement co-E. Bird co-Bird [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The graph Bird and its complement co-Bird. Let E-graph and Bird be the graphs in Figures 4 and 5, respectively. In this paper, we prove the following theorems. Theorem 1.10. E-graph has the Erd˝os-Hajnal property. Theorem 1.11. Bird has the Erd˝os-Hajnal property. Since both E-graph and Bird contain an induced P5, both Theorem 1.10 and Theorem 1.11 generalize the main result by Nguyen, Scott and Seymour [1… view at source ↗
Figure 6
Figure 6. Figure 6: A graph H with the Erd˝os-Hajnal property. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: H0, H1 and H5. Let us first record the following simple lemma. Lemma 6.3. {H5, co-E} has the Erd˝os-Hajnal property. 26 [PITH_FULL_IMAGE:figures/full_fig_p026_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Induced co-Es in the proof of Claim 6.4.1 where the blue line is the subpath of P. Suppose first that u is complete to C. By Claim 6.4.1 (2) with P = v ′ j − vj − vj+1 − vj+2, we have u is adjacent to v ′ j for each j ∈ [5]. If u is not adjacent to w, then {v ′ 1 , u, v1, v2, v3, w} induces a co-E, a contradiction. So we may assume uw ∈ E(G). Then u is complete to H5, a contradiction. So u is not complete … view at source ↗
Figure 9
Figure 9. Figure 9: ), a contradiction. This proves Claim 6.5.1 (2). ■ a b c y x u Proof of Claim 6.5.1 (1) a b c d y u Proof of Claim 6.5.1 (2) [PITH_FULL_IMAGE:figures/full_fig_p030_9.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. A Single-Exponential Erd\H{o}s--Hajnal Bound for Graphs of Bounded VC-Dimension

    math.CO 2026-07 accept novelty 6.0

    Every n-vertex graph of VC-dimension ≤ d has a homogeneous set of size at least n^{(C d)^{-d}} for an absolute constant C.

Reference graph

Works this paper leans on

17 extracted references · 2 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    N. Alon, J. Pach, and J. Solymosi. Ramsey-type theorems with forbidden subgraphs. Combinatorica, 21(2):155-170, 2001

    2001

  2. [2]

    J. A. Bondy and U. S. R. Murty.Graph Theory. Springer, 2008

    2008

  3. [3]

    Bousquet, A

    N. Bousquet, A. Lagoutte, and S. Thomass´ e. The Erd˝ os–Hajnal conjecture for paths and antipaths.Journal of Combinatorial Theory, Series B, 113:261-264, 2015

    2015

  4. [4]

    Buci´ c, J

    M. Buci´ c, J. Fox, and H. T. Pham. Equivalence between Erd˝ os-Hajnal and polynomial R¨ odl and Nikiforov conjectures. arXiv:2403.08303 [math.CO], 2024

    work page arXiv 2024

  5. [5]

    Buci´c, T Nguyen, A Scott and P

    M. Buci´c, T Nguyen, A Scott and P. Seymour. A log log step towards Erd˝ os-Hajnal. International Mathematics Research Notices, 9991-10004, 2024

    2024

  6. [6]

    Chudnovsky and S

    M. Chudnovsky and S. Safra. The Erd˝ os-Hajnal conjecture for bull-free graphs.Journal of Combinatorial Theory, Series B, 98(6):1301-1310, 2008

    2008

  7. [7]

    Chudnovsky, A

    M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Pure pairs. I. Trees and linear anti-complete pairs.Advances in Mathematics, 375:107396, 20, 2020

    2020

  8. [8]

    Chudnovsky, A

    M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Erd˝ os-Hajnal for graphs with no 5-hole.Proceedings of the London Mathematical Society, 126(3):997-1014, 2023

    2023

  9. [9]

    P. Erd˝ os. Some remarks on the theory of graphs.Bulletin of the American Mathematical Society, 53:292-294, 1947

    1947

  10. [10]

    Erd˝ os and A

    P. Erd˝ os and A. Hajnal. Ramsey-type theorems.Discrete Applied Mathematics, 25:37-52, 1989

    1989

  11. [11]

    Erd˝ os and G

    P. Erd˝ os and G. Szekeres. A combinatorial problem in geometry.Compositio Mathematica, 2:464-470, 1935. 32

    1935

  12. [12]

    Induced subgraph density. IV. New graphs with the Erd\H{o}s-Hajnal property

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraphs density. IV. New graphs with the Erd˝ os-Hajnal property. arXiv:2307.06455 [math.CO], 2023

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  13. [13]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. VI. Bounded VC- dimension.Advances in Mathematics, 482, no. A, 110601, 2025

    2025

  14. [14]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. VII. The five-vertex path. Proceedings of the London Mathematical Society, 132(3):e70133, 2026

    2026

  15. [15]

    Nikiforov

    V. Nikiforov. Edge distribution of graphs with few fopies of a given graph.Combinatorics, Probability and Computing, 15(6):895-902, 2006

    2006

  16. [16]

    F. P. Ramsey. On a problem of formal logic.Proceedings of the London Mathematical Society, 30:264-286, 1930

    1930

  17. [17]

    V. R¨ odl. On universality of graphs with uniformly distributed edges.Discrete Mathematics, 59(1-2):125-134, 1986. 33

    1986

This paper was first reviewed by grok-4.3 on June 28, 2026.