Komlós–Sós conjecture on degree-sequence conditions for tree embeddings

Let GG be a graph on nn vertices, and let kk be a positive integer. A tree with kk edges has k+1k+1 vertices. Komlós–Sós conjecture. If at least n/2n/2 vertices of GG have degree at least kk, then GG contains every tree with kk edges. This conjecture is presented as a generalization of a theorem of Zhao and is part of the effort to characterize degree conditions forcing tree embeddings; the source does not report a resolution.

Sources & referencesView supporting material

Primary source

Daniela Kühn and Deryk Osthus, “Embedding large subgraphs into dense graphs”, arXiv:0901.3541 (2009).

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.