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

Frédéric Havet, Bruce Reed, Maya Stein, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

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 ⌊2m/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 ⌊2m/3⌋ by (1−γ)m holds.
Original languageEnglish
Pages (from-to)131-158
Number of pages28
JournalJournal of Graph Theory
Volume94
Issue number1
DOIs
Publication statusPublished - May 2020

Cite this