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

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
Number of pages28
JournalJournal of Graph Theory
DOIs
Publication statusAccepted/In press - 2019

Cite this

Havet, Frédéric ; Reed, Bruce ; Stein, Maya ; Wood, David R. / A variant of the Erdős‐Sós conjecture. In: Journal of Graph Theory. 2019.
@article{02802012f00c46e882c843904b2f5cb4,
title = "A variant of the Erdős‐S{\'o}s conjecture",
abstract = "A well‐known conjecture of Erdős and S{\'o}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.",
author = "Fr{\'e}d{\'e}ric Havet and Bruce Reed and Maya Stein and Wood, {David R}",
year = "2019",
doi = "10.1002/jgt.22511",
language = "English",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "John Wiley & Sons",

}

A variant of the Erdős‐Sós conjecture. / Havet, Frédéric; Reed, Bruce; Stein, Maya; Wood, David R.

In: Journal of Graph Theory, 2019.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Havet, Frédéric

AU - Reed, Bruce

AU - Stein, Maya

AU - Wood, David R

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

U2 - 10.1002/jgt.22511

DO - 10.1002/jgt.22511

M3 - Article

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

ER -