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
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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 : Tuesday, May 26, 2020 - 6:50:53 PM
Document(s) archivé(s) le : 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, 2019, 94 (1), pp.131-158. ⟨10.1002/jgt.22511⟩. ⟨hal-02497401⟩

Share

Metrics

Record views

74

Files downloads

282