The constant-degree-tree version of the 2k2kk2\frac{k}{2} conjecture

Let k,ΔNk,\Delta\in\mathbb{N}, and let GG be a graph. Write δ(G)\delta(G) and Δ(G)\Delta(G) for the minimum and maximum degrees of GG, respectively. Constant-degree-tree conjecture. If

δ(G)k2andΔ(G)2(11Δ)k,\delta(G)\geq \frac{k}{2}\qquad\text{and}\qquad \Delta(G)\geq 2\left(1-\frac{1}{\Delta}\right)k,

then GG contains every tree TT with kk edges satisfying Δ(T)Δ\Delta(T)\leq\Delta.

This is a bounded-maximum-degree refinement of the 2k2kk2\frac{k}{2} conjecture, weakening the required host maximum degree for trees of maximum degree at most Δ\Delta. The source gives an approximate result supporting it, but the exact conjecture remains open.

Sources & referencesView supporting material

Primary source

Guido Besomi, Matías Pavez-Signé and Maya Stein, “Degree conditions for embedding trees”, arXiv:1805.07338 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.