A variant of the Erdős‐Sós conjecture - Archive ouverte HAL Access content directly
Journal Articles Journal of Graph Theory Year : 2020

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

(1) , (1) , (2) , (3)
1
2
3
Frédéric Havet
Bruce Reed
David R Wood
• Function : Author

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.

Dates and versions

hal-02497401 , version 1 (03-03-2020)

Identifiers

• HAL Id : hal-02497401 , version 1
• DOI :

Cite

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

48 View