The large first- and second-neighbourhood conjecture for tree embeddings

Let kNk\in\mathbb{N}, and let GG be a graph. For a vertex xV(G)x\in V(G), let N(x)N(x) denote its neighbourhood and let N2(x)N_2(x) denote its second neighbourhood. Large first- and second-neighbourhood conjecture. If

δ(G)k2\delta(G)\geq \frac{k}{2}

and there is a vertex xx such that

min{N(x),N2(x)}4k3,\min\{|N(x)|,|N_2(x)|\}\geq \frac{4k}{3},

then GG contains every tree with kk edges.

This offers a local alternative to imposing a large maximum degree, by requiring both the first and second neighbourhoods of one vertex to be large. The source presents it as an open approach to avoiding known extremal obstructions; no resolution is supplied.

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.