Skip to Main content Skip to Navigation
Journal articles

A variant of the Erdős‐Sós conjecture

Frédéric Havet 1 Bruce Reed 1 Maya Stein 2 David Wood 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding $m−1$ contains every tree with m edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding m and minimum degree at least $[\frac{2m}{3}]$ contains every tree with m edges. As evidence for our conjecture we show (i) for every m there is a g(m) such that the weakening of the conjecture obtained by replacing the first m by g(m) holds, and (ii) there is a $\gamma > 0$ such that the weakening of the conjecture obtained by replacing $[\frac{2m} {3}$ by $(1 − \gamma)m$ holds.
Document type :
Journal articles
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-02497401
Contributor : Frederic Havet <>
Submitted on : Tuesday, March 3, 2020 - 4:10:23 PM
Last modification on : Wednesday, December 2, 2020 - 9:28:42 AM
Long-term archiving on: : Thursday, June 4, 2020 - 5:33:16 PM

File

ErdosSosVariant.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Frédéric Havet, Bruce Reed, Maya Stein, David Wood. A variant of the Erdős‐Sós conjecture. Journal of Graph Theory, Wiley, 2020, 94 (1), pp.131-158. ⟨10.1002/jgt.22511⟩. ⟨hal-02497401⟩

Share

Metrics

Record views

106

Files downloads

402