Rainbow Erd\H{o}s-S\'os Conjectures

Dylan King; Nicholas Crawford; Sam Spiro

REVIEW 3 major objections 5 minor 20 references

Rainbow Erd\H{o}s-S\'os Conjectures

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read This paper proposes a rainbow Erdős–Sós conjecture for hypercubes: every $k$-edge tree should have rainbow extremal number $\frac{k-1}{2}2^n$ in $Q_n$; it proves the exact value for $P_3$, $P_4$, and leaf-rich trees, and bounds all trees…

desk verdict The central conjecture is false as stated for small n, but the fix is easy and the partial results are solid enough to justify a serious referee. read the letter →

arxiv 2502.00135 v1 pith:UBZATLOY submitted 2025-01-31 math.CO

Nicholas Crawford , Dylan King , Sam Spiro This is my paper · ORCID

classification math.CO MSC 05C3505C0505C15

keywords rainbowextremalnumberErdős–SósconjecturehypercubetreeembeddingproperedgecoloringTuránproblemminimumdegree

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 classical Erdős–Sós conjecture says that the ordinary extremal number of a $k$-edge tree $T$ depends only on $k$, not on the tree's shape. This paper asks whether the same structure-independence can hold for rainbow extremal numbers, where edges must be properly colored and no rainbow copy of $T$ may appear. The answer in complete graphs is no: a star and a path already have different rainbow extremal numbers, so the paper changes the host to the $n$-dimensional hypercube $Q_n$, which is 1-factorizable and therefore gives both a natural lower bound and a plausible setting for uniformity. The paper's central conjecture is that $\mathrm{ex}^*(Q_n,T)=\frac{k-1}{2}2^n$ for every $k$-edge tree $T$, and it verifies this exactly for the 2-edge and 3-edge paths and for any tree with a vertex adjacent to more than $\frac{3}{4}k$ leaves, while proving the general upper bound $\mathrm{ex}^*(Q_n,T)<(2k-1)2^n$. A second conjecture, that the rainbow minimum-degree parameter satisfies $\delta^*(Q_n,T)=k-1$ for every tree, is verified for paths, long pendant paths, leaf-rich trees, and spiders with legs of even length or of length 3.

What carries the argument

The central object is an auxiliary graph $H$ built from a leaf-ordering of the forbidden tree $T$. Given a leaf-ordering $x_0,\dots,x_k$ of a $k$-edge tree with edges $e_i=x_{i'}x_i$, construct $H_0$ so that no edge $e_j$ has too many earlier $H_0$-neighbors, then form $H$ by adding edges between pairs of tree edges that share a vertex. Lemma 5 states that if every path of length $2\ell$ in $T$ induces a subgraph of $H$ on its edge-vertices with chromatic number at least $\ell+1$, then $\delta^*(Q_n,T)\le k-1$. The lemma works by greedily embedding $T$ into a properly colored minimum-degree-$k$ subgraph of $Q_n$, using the auxiliary graph to control which coordinates and colors are forbidden; a cycle in the embedding would let one color the path's edges with $\ell$ coordinates, contradicting the chromatic condition. Most of Theorem 3 is a sequence of explicit constructions of $H_0$ for the relevant tree families, verifying this chromatic bottleneck.

What would settle it

A direct refutation would be a properly edge-colored subgraph of $Q_n$ with $n\ge k-1$, minimum degree $k$, and no rainbow copy of some $k$-edge tree $T$; that would disprove Conjecture 3 and imply Lemma 5's chromatic condition fails for $T$. Short of that, a computer search over all trees on $k\le 8$ edges can check Lemma 5 directly: find a leaf-ordering and a $2\ell$-edge path whose auxiliary induced subgraph has chromatic number at most $\ell$, which would break the greedy-embedding proof for that tree. For Conjecture 2, the corresponding test is to find a properly colored subgraph of $Q_n$ with more than $\frac{k-1}{2}2^n$ edges and no rainbow $T$.

Watch

Extended reading notes

Core claim

The paper's central proposal is a rainbow analogue of the Erdős–Sós conjecture with the hypercube as host: for every $k$-edge tree $T$, the relative rainbow extremal number $\mathrm{ex}^*(Q_n,T)$ should equal $\frac{k-1}{2}2^n$, the value already forced by a star. Because $Q_n$ decomposes into $n$ perfect matchings (one per coordinate), taking any $k-1$ of them gives a properly colored $(k-1)$-regular subgraph with no rainbow $k$-edge graph, supplying the lower bound; the content is matching upper bounds. The paper proves the equality for $T=P_3$, $T=P_4$, and for trees in which some vertex is adjacent to more than $\frac{3}{4}k$ leaves, and a universal upper bound within a factor of about 4 for every tree. On the minimum-degree side, it proves $\delta^*(Q_n,T)=k-1$ for paths, trees with a pendant path of at least $\frac{3k-1}{4}$ edges, trees with at least $\frac{k-1}{2}$ leaves, spiders with even-length legs, and spiders with legs of length 3. The heart of the upper-bound arguments is a greedy embedding lemma that reduces the problem to a purely combinatorial condition on the forbidden tree: each even-length path of edges must force its auxiliary graph to demand more colors than half the path length.

Load-bearing premise

The load-bearing premise is that every tree can be leaf-ordered so that, for every even-length path of edges, the auxiliary graph built from that path must need at least one more color than half the path's length; if any tree fails this condition, the greedy embedding proof of $\delta^*(Q_n,T)=k-1$ collapses.

Editorial extensions

If this is right

If Conjecture 2 holds, then in the hypercube the rainbow extremal number of every $k$-edge tree equals the ordinary extremal number of the star, $\frac{k-1}{2}2^n$; the rainbow constraint would impose no extra structural cost for trees in this host.
The universal bound $\mathrm{ex}^*(Q_n,T)<(2k-1)2^n$ gives the first linear-in-$|V(Q_n)|$ upper bound valid for every tree, with constant $2k-1$; this is the hypercube counterpart of the folklore bound $\mathrm{ex}(n,T)\le (k-1)n$ in complete graphs.
The minimum-degree equality $\delta^*(Q_n,T)=k-1$ for the listed families means any rainbow-$T$-free properly colored subgraph of $Q_n$ must have a vertex of degree at most $k-1$, so the extremal subgraphs for minimum degree are exactly the unions of $k-1$ coordinate matchings.
The exact values for $P_3$ and $P_4$ establish the first path cases of the new conjecture: $\mathrm{ex}^*(Q_n,P_3)=2^n$ and $\mathrm{ex}^*(Q_n,P_4)=\frac{3}{2}2^n$.

Reading between the lines

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

A natural testable extension is to run a computer search over all trees on small $k$, checking whether every leaf-ordering satisfies Lemma 5's chromatic condition; if a tree fails it, that indicates where the greedy method—and possibly the conjecture itself—needs a new idea.
Because Theorem 6 is proved for general $K_{2,r}$-free hosts rather than only $Q_n$, the exact value $\frac{k-1}{2}|V(G)|$ for leaf-rich trees should extend to any $K_{2,r}$-free graph with $k-1$ disjoint perfect matchings, suggesting a broad family of hosts beyond the hypercube would satisfy a rainbow Erdős–Sós statement.
The proof for spiders with legs of length 3 (Theorem 3 Part 4) checks the finitely many cases of the auxiliary chromatic condition by inspection; an automated check of those four configurations would verify the last case directly.
The paper notes that adding a single diagonal edge to $Q_n$ destroys the lower-bound construction, which suggests the exact equality is fragile under small perturbations of the host; examining which subgraphs of the diagonal-augmented cube restore it could clarify what property of $Q_n$ is doing the work.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

The paper has a load-bearing flaw: Conjecture 2 as stated is false. For n=2 and T=P4 (k=4), the predicted value is 6 but Q2 has only 4 edges. The issue is that the lower-bound construction needs k-1 disjoint perfect matchings, i.e., n≥k-1, but the conjecture is written for all n. This is not a minor typo; it makes the central claim false. The fix is straightforward: restrict to n≥k-1 or state the asymptotic form.

That said, what is actually new is worth taking seriously. The paper introduces the relative rainbow extremal number on the hypercube, proposes that it satisfies an Erdős-Sós type statement, and proves the first exact results for small paths and trees with many leaves. The lower bounds from coordinate matchings are correct for n≥k-1. Lemma 5 is a clever greedy framework for upper bounds on δ*, and the verifications for paths, stars, and spiders are non-trivial. The universal upper bound ex*(Q_n,T)<(2k-1)2^n is a useful first step.

The soft spots are real but fixable. Besides the small-n issue, the many-leaves greedy count contains an algebraic error: (k-m)-2(k-m-ℓ) does not equal ℓ. And the proof for 3-spiders relies on 'inspection' of four cases, which is underdeveloped. There also seem to be typos in the statement of Theorem 2 part 1 (P3 value). None of these undermine the core idea, but they need attention.

Who should read this? Extremal graph theorists and rainbow Turán people. The concept of relative rainbow extremal number is likely to be useful beyond this paper. It deserves a serious referee, but only after the authors fix the statements and the arithmetic. As written, I would not accept it; I would send it back for revision.

Referee Report

3 major / 5 minor

Summary. The paper defines relative rainbow extremal numbers ex*(G,T) and the associated minimum-degree parameter δ*(G,T), and conjectures that for the hypercube Q_n these depend only on the number of edges of the tree T, with values (k−1)/2·2^n and k−1 respectively. The authors prove Theorem 2 (equality of ex*(Q_n,T) with this value for P3, P4, and trees with a vertex adjacent to more than 3/4 of its edges as leaves, plus a universal upper bound) and Theorem 3 (equality δ*(Q_n,T)=k−1 for paths, many-leaf trees, and certain spiders), relying on a general host-graph result (Theorem 6) and a greedy embedding lemma (Lemma 5). Lower bounds come from the 1-factorization of Q_n into coordinate matchings.

Significance. If the conjectures hold with the necessary dimension restriction n≥k−1, the paper identifies a natural host graph in which the rainbow extremal number regains the uniformity conjectured by Erdős–Sós. The proposed statements are clean and the partial verifications are nontrivial; the lower-bound construction by coordinate matchings is correct and elementary, and the universal bound ex*(Q_n,T)<(2k−1)2^n is a useful quantitative result. The paper also introduces a general framework for ex* on K3-free hosts that may be of independent interest. However, as written the central conjecture is false for small n, and one of the main proof lemmas has a serious gap.

major comments (3)

[Conjecture 2 / Theorem 2] The literal statements of Conjecture 2, Conjecture 3, and Theorem 2 parts 1–3 are false when n<k−1, because the claimed value (k−1)/2·2^n exceeds the total number of edges of Q_n, namely n·2^{n−1}. For example, for n=2 and T=P4 (k=4), Q2 has only 4 edges, so ex*(Q2,P4)≤4, whereas the conjecture predicts 6; likewise δ*(Q2,T)≤2<3=k−1. The lower-bound constructions require k−1 disjoint perfect matchings, so the dimension hypothesis n≥k−1 is necessary. Please add this restriction to all relevant conjectures and theorems, or explicitly state the intended asymptotic form.
[Section 3.2, Lemma 5] The proof of Lemma 5's cycle-prevention step is not justified. It asserts that the coordinate assignment of the embedded edges is a proper vertex coloring of the auxiliary graph H, so that the chromatic hypothesis χ(H[P])≥ℓ+1 contradicts the fact that a cycle in Q_n uses at most ℓ coordinates. However, coordinates of two embedded edges are distinct only when the edges share a vertex in Q_n. For edges joined by H0 but disjoint in T, their images can share a coordinate when the corresponding path folds to a cycle (for instance, edges at even distance along the path can have identical coordinates in a folded cycle). Thus the coordinate map need not be a proper vertex coloring of H, and the claimed contradiction does not follow. Since Theorem 3 depends on Lemma 5, this gap must be repaired.
[Section 4.2, proof of Theorem 6(4)] The greedy leaf-embedding count contains an algebraic error: (k−m)−2(k−m−ℓ) does not equal ℓ. The intended argument appears to be that after using the k−m unused neighbors of v0 and avoiding the colors of the k−m−ℓ non-adjacent edges, one has (k−m)−(k−m−ℓ)=ℓ valid choices; the extra factor 2 and the mention of 'coordinate' are spurious, since Theorem 6 is stated for general K_{2,r}-free graphs rather than for hypercubes. Please correct the calculation and clarify the counting.

minor comments (5)

[Section 2 (Theorem 2 and Theorem 3)] The statements of Theorem 2 and Theorem 3 should explicitly include the hypothesis n≥k−1; as written, the equalities are impossible when k−1>n because δ*(Q_n,T)≤n and ex*(Q_n,T)≤e(Q_n).
[Section 3.2, proof of Theorem 3(4)] The verification of the four cases in Figure 5 is left to 'inspection'; please expand with a short written argument or a more detailed caption explaining the chromatic-number computations for each case.
[Section 4.2, proof of Theorem 6(4)] The phrase 'color and coordinate' is confusing because coordinates are only defined for hypercubes, whereas Theorem 6 is stated for arbitrary K_{2,r}-free graphs; please remove the coordinate talk or explicitly restrict that step to Q_n.
[Section 3.2] The sentence 'While not a formal tool, these pictograms will help clarify the more delicate cases remaining in Theorem 3' appears twice; please delete the duplicate.
[References] Please verify reference [1]; the displayed year (1989) appears inconsistent with the volume of Israel Journal of Mathematics cited.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivations are self-contained and do not reduce to their own inputs.

full rationale

I walked the derivation chain for every main claim. The paper defines the relative rainbow extremal number ex*(G,F) and the minimum-degree variant independently of any target value, then proves bounds from first principles. The universal lower bound ex*(Q_n,T) >= (k-1)/2 * 2^n follows from Proposition 1, which observes that k-1 disjoint perfect matchings use (k-1)/2 * |V(G)| edges and admit a proper (k-1)-coloring, so no k-edge subgraph can be rainbow. The upper bounds in Theorems 2 and 6 are obtained through explicit greedy-embedding arguments (Lemma 5, Lemma 7, Lemma 8, Lemma 9) with fully stated hypotheses; no fitted parameter is renamed as a prediction, and no theorem is assumed in a form equivalent to its conclusion. Theorem 3 likewise reduces each case to checking a stated auxiliary graph chromatic condition in Lemma 5, and the cited external results (Erdős-Gallai, Maamoun-Meyniel, hypercube factorization) are independent support rather than self-citations. The authors do not cite their own prior work for any load-bearing step. The skeptic's objection that Conjecture 2 fails literally when n < k-1 because the claimed value exceeds e(Q_n) is a genuine correctness issue about the stated range of n, not a circularity, since it does not involve the conclusion being assumed as an input or made true by definition. Similarly, the 'by inspection' case check in Theorem 3 Part 4 is a possible proof-gap concern, not a circularity. Under the required standard, no step exhibits the reduction of a claimed result to its own input, so the appropriate finding is no significant circularity.

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

The central derivations rest on standard hypercube facts, the leaf-ordering lemma, and two cited external results. No new physical or mathematical entity is postulated. The only hidden input is the unstated large-n assumption; all exponents are integer tree sizes, not fitted constants.

assumptions (6)

standard math Hypercube Q_n is 1-factorizable into n perfect matchings (coordinate matchings).
Used in Proposition 1 and throughout for lower bounds; a basic property of Q_n.
standard math Every tree has a leaf-ordering in which each non-initial vertex has exactly one earlier neighbor.
Stated in Section 2 and used by every greedy embedding proof.
standard math Maamoun-Meyniel's construction: K_{2p} has a proper edge-coloring with no rainbow Hamiltonian path.
Cited as [17], used in Proposition 4 Part 3 to show δ*(n,P_k) can exceed δ*(n,star).
standard math Erdős-Gallai bound on path extremal numbers.
Cited as [6], used to motivate the folklore δ(n,T) discussion; not a load-bearing dependency for the new theorems.
standard math Any two vertices of Q_n have at most two common neighbors; hence Q_n is K3-free and K2,3-free.
Used to apply Theorem 6 Parts 2-4 to Q_n; elementary property of hypercubes.
domain assumption The host dimension n is taken large enough that k-1 disjoint coordinate matchings exist; the statements as written "for each n∈N" are false when n<k-1.
The lower bound construction and Conjectures 2-3 require n≥k-1; the paper never states this restriction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Rainbow Erd\H{o}s-S\'os Conjectures." pith.science (2026). https://pith.science/paper/UBZATLOY

@misc{pith2026250200135,
  author       = {Pith},
  title        = {Pith review of: Rainbow Erd\Hos-S\'os Conjectures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UBZATLOY}},
  note         = {Machine review of arXiv:2502.00135}
}

abstract

An edge colored graph is said to contain rainbow-$F$ if $F$ is a subgraph and every edge receives a different color. In 2007, Keevash, Mubayi, Sudakov, and Verstra\"ete introduced the \emph{rainbow extremal number} $\mathrm{ex}^*(n,F)$, a variant on the classical Tur\'an problem, asking for the maximum number of edges in a $n$-vertex properly edge-colored graph which does not contain a rainbow-$F$. In the following years many authors have studied the asymptotic behavior of $\mathrm{ex}^*(n,F)$ when $F$ is bipartite. In the particular case that $F$ is a tree $T$, the infamous Erd\"os-S\'os conjecture says that the extremal number of $T$ depends only on the size of $T$ and not its structure. After observing that such a pattern cannot hold for $\mathrm{ex}^*$ in the usual setting, we propose that the relative rainbow extremal number $\mathrm{ex}^*(Q_n,T)$ in the $n$-dimensional hypercube $Q_n$ will satisfy an Erd\"os-S\'os type Conjecture and verify it for some infinite families of trees $T$.

Figures

Figures reproduced from arXiv: 2502.00135 by the authors.

**Figure 1.** The four problems considered here for a k-edge tree T The natural problem is, in the spirit of Question 1, if there are hosts G where δ(G, T ) depends only on the number of edges in T . It turns out that δ ∗ (n, T ), like ex∗ (n, T ), is sensitive to the structure of T . Andersen conjectured [2] that any proper edge-coloring of Kn contains a rainbow path on n − 1 vertices, after Maamoun and Meyniel [17], disproving … view at source ↗

**Figure 4.** Proof of Theorem 3 Part 4. We use very similar notation to the previous problem, with vertices x0 and x (s) 1 , x (s) 2 , x (s) 3 for 1 ≤ s ≤ t. For our ordering we take {x0, x (1) 1 , x (2) 1 , . . . , x (t) 1 , x (1) 2 , . . . , x (t) 2 , x (t) 3 , . . . , x (1) 3 }. Note that the outermost t edges will be embedded in reverse. As we have seen before, for m = 3t+1 2 − t we can make the first t + m edges a cliqu… view at source ↗

**Figure 5.** From top to bottom: 1) r, s ≤ m 2) m < r, s 3) r ≤ m < s with r ≤ t − s 4) r ≤ m < s with r > t − s 9 [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗

Figures from the paper (4 more)

**Figure 6.** Figure 6: The fork graph 10 [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]

**Figure 7.** Figure 7: Then if uv1 has color A, and uv2, uv3, uv4 have colors B, C, D, then at least one of {B, C, D}, say B, does not appear on the edges v1W. It is possible that one of the edges v2W2 has color A, but at least one of them avoids both A and B. Finally one of the two edges v1…

**Figure 7.** Figure 7: The case when W1 does not meet any other Wi . Note that the w vertices on the right hand side may be identified if they are attached to distinct vi . u v1 v2 v3 v4 A B C D w1,1 = w4,2 w1,2 = w2,1 w2,2 = w3,1 w3,2 = w4,1 [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]

**Figure 8.** Figure 8: The case when the Wi intersect cyclically. 12 [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

N. Alon, A. Pokrovskiy, and B. Sudakov. Random subgraphs of p roperly edge-coloured complete graphs and long rainbow cycles. Israel Journal of Mathematics , 222(1):317–331, 1989

work page 1989
[2]

Andersen

L. Andersen. Hamilton circuits with many colours in properly edge- coloured complete graphs. Mathe- matica Scandinavica, 51(2):5–14, 1989

work page 1989
[3]

Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

J´ ozsef Balogh, Ping Hu, Bernard Lidick´ y, and Hong Liu. Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube. European Journal of Combinatorics , 35:75–85, 2014. Selected Papers of EuroComb’11

work page 2014
[4]

The erd˝ os-s´ os conjecture for graphs of girth 5

Stephan Brandt and Edward Dobson. The erd˝ os-s´ os conjecture for graphs of girth 5. Discrete Mathe- matics, 150(1):411–414, 1996

work page 1996
[5]

Subgraphs of a hypercube containing no small eve n cycles

Fan RK Chung. Subgraphs of a hypercube containing no small eve n cycles. Journal of Graph Theory , 16(3):273–286, 1992

work page 1992
[6]

Erd¨ os and T

P. Erd¨ os and T. Gallai. On maximal paths and circuits of graphs. Acta Mathematica Academiae Scientiarum Hungarica, 10(3):337–356, 1959

work page 1959
[7]

On the rain bow tur´ an number of paths

Beka Ergemlidze, Ervin Gy¨ ori, and Abhishek Methuku. On the rain bow tur´ an number of paths. Elec- tronic Journal of Combinatorics , 26, 2019

work page 2019
[8]

Expanding graphs contain all small trees

Joel Friedman and Nicholas Pippenger. Expanding graphs contain all small trees. Combinatorica, 7(1):71–76, 1987

work page 1987

Show all 20 references

[9]

G. Hahn. Un jeu de coloration. in regards sur la theorie des graph es. Actes du Colloque de Cerisy , 12:18, 1980

1980
[10]

P. E. Haxell. Tree embeddings. Journal of Graph Theory , 36(3):121–130, 2001

2001
[11]

Saturated subgraphs of the hypercube

J Robert Johnson and Trevor Pinto. Saturated subgraphs of the hypercube. Combinatorics, Probability and Computing , 26(1):52–67, 2017

2017
[12]

Asymptotic solution for a new class of forbidden r-graphs

A.F Johnston. Asymptotic solution for a new class of forbidden r-graphs. Combinatorica, 9:207–215, 1989

1989
[13]

Rainbow tur ´ an problems for paths and forests of stars

Daniel Johnston, Cory Palmer, and Amites Sarker. Rainbow tur ´ an problems for paths and forests of stars. Electronic Journal of Combinatorics , 24, 2017

2017
[14]

Lower bounds for rainbow tur´ an numbers of paths and other trees

Daniel Johnston and Puck Rombach. Lower bounds for rainbow tur´ an numbers of paths and other trees. Australian Journal of Combinatorics , 78(1):61–72, 2020

2020
[15]

Micha perles’ geometric proof of the erdos-sos conje cture for caterpillars, Sep 2017

Gil Kalai. Micha perles’ geometric proof of the erdos-sos conje cture for caterpillars, Sep 2017

2017
[16]

Rainbow tur´ an problems

Peter Keevash, Dhruv Mubayi, Benny Sudakov, and Jacques V erstra¨ ete. Rainbow tur´ an problems. Combinatorics, Probability and Computing , 16(1):109–126, 2007

2007
[17]

Maamoun and H

M. Maamoun and H. Meyniel. On a problem of g. hahn about coloure d hamiltonian paths in k2t. Discrete Mathematics, 51(2):213–214, 1984

1984
[18]

The erd˜ os-s´ os conjecture for trees o f diameter four

Andrew McLennan. The erd˜ os-s´ os conjecture for trees o f diameter four. Journal of Graph Theory , 49(4):291–301, aug 2005

2005
[19]

Bounding the size of squa re-free subgraphs of the hypercube

Andrew Thomason and Peter Wagner. Bounding the size of squa re-free subgraphs of the hypercube. Discrete Mathematics, 309(6):1730–1735, 2009

2009
[20]

On the erd¨ os-s´ os conjecture.Journal of Graph Theory , 21(2):229–234, 1996

Mariusz Wo´ zniak. On the erd¨ os-s´ os conjecture.Journal of Graph Theory , 21(2):229–234, 1996. 14

1996

Pith tools

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

[1] [1]

N. Alon, A. Pokrovskiy, and B. Sudakov. Random subgraphs of p roperly edge-coloured complete graphs and long rainbow cycles. Israel Journal of Mathematics , 222(1):317–331, 1989

work page 1989

[2] [2]

Andersen

L. Andersen. Hamilton circuits with many colours in properly edge- coloured complete graphs. Mathe- matica Scandinavica, 51(2):5–14, 1989

work page 1989

[3] [3]

Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

J´ ozsef Balogh, Ping Hu, Bernard Lidick´ y, and Hong Liu. Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube. European Journal of Combinatorics , 35:75–85, 2014. Selected Papers of EuroComb’11

work page 2014

[4] [4]

The erd˝ os-s´ os conjecture for graphs of girth 5

Stephan Brandt and Edward Dobson. The erd˝ os-s´ os conjecture for graphs of girth 5. Discrete Mathe- matics, 150(1):411–414, 1996

work page 1996

[5] [5]

Subgraphs of a hypercube containing no small eve n cycles

Fan RK Chung. Subgraphs of a hypercube containing no small eve n cycles. Journal of Graph Theory , 16(3):273–286, 1992

work page 1992

[6] [6]

Erd¨ os and T

P. Erd¨ os and T. Gallai. On maximal paths and circuits of graphs. Acta Mathematica Academiae Scientiarum Hungarica, 10(3):337–356, 1959

work page 1959

[7] [7]

On the rain bow tur´ an number of paths

Beka Ergemlidze, Ervin Gy¨ ori, and Abhishek Methuku. On the rain bow tur´ an number of paths. Elec- tronic Journal of Combinatorics , 26, 2019

work page 2019

[8] [8]

Expanding graphs contain all small trees

Joel Friedman and Nicholas Pippenger. Expanding graphs contain all small trees. Combinatorica, 7(1):71–76, 1987

work page 1987