Besomi–Pavez-Signé–Stein second-neighbourhood conjecture for tree embeddings

Let kk be a positive integer. For a graph GG and a vertex xV(G)x\in V(G), let NG(x)N_G(x) be the neighbourhood of xx, and let NG2(x)N_G^2(x) be the set of vertices other than xx sharing a common neighbour with xx. Besomi–Pavez-Signé–Stein second-neighbourhood conjecture. If

δ(G)k/2\delta(G)\geqslant k/2

and GG contains a vertex xx such that

min{NG(x),NG2(x)}4k/3,\min\{|N_G(x)|,|N_G^2(x)|\}\geqslant 4k/3,

then GG contains a copy of every tree with kk edges. This replaces a maximum-degree hypothesis by a local first- and second-neighbourhood condition; no resolution is supplied in the source, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Alexey Pokrovskiy, Leo Versteegen and Ella Williams, “Embedding trees using minimum and maximum degree conditions”, arXiv:2512.16799 (2025).

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.