A variant of the Erdős‐Sós conjecture. Issue 1 (8th November 2019)

• Record Type: Journal Article
• Authors: Havet, Frédéric; Reed, Bruce; Stein, Maya; Wood, David R.
• Is Part Of: Journal of graph theory. Volume 94:Issue 1(2020)
• Page Start: 131
• Page End: 158
• Publication Date: 2019-11-08
• Subjects: Erdős‐Sós conjecture -- graph theory; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22511
• Languages: English
• ISSNs: 0364-9024

Abstract

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 ⌊ 2 m / 3 ⌋ contains every tree with m edges. As evidence for our conjecture we show (a) 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 (b) there is a γ > 0 such that the weakening of the conjecture obtained by replacing ⌊ 2 m / 3 ⌋ by ( 1 − γ ) m holds.