A variant of the Erdős‐Sós conjecture - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Graph Theory Année : 2020

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

Résumé

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.
Fichier principal
Vignette du fichier
ErdosSosVariant.pdf (358.37 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
66 Consultations
201 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More