The constant-degree-tree version of the 2k2k–k2\frac{k}{2} conjecture

About 8 years old · traced to

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(1−1Δ)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 2k2k–k2\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.

References

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.