The interpolating degree-condition conjecture for tree embeddings

Let kNk\in\mathbb{N}, let 0α120\leq\alpha\leq \frac{1}{2}, and let GG be a graph. Write δ(G)\delta(G) and Δ(G)\Delta(G) for the minimum and maximum degrees of GG, respectively. Interpolating degree-condition conjecture. If

δ(G)(1+α)k2andΔ(G)2(1α)k,\delta(G)\geq (1+\alpha)\frac{k}{2}\qquad\text{and}\qquad \Delta(G)\geq 2(1-\alpha)k,

then GG contains every tree with kk edges.

This conjecture interpolates between the degree requirements in the 2k2kk2\frac{k}{2} conjecture as α\alpha varies, trading a stronger minimum-degree condition for a weaker maximum-degree condition. The source cites related forthcoming work and leaves this general statement 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.