Minimum-semidegree conjecture for balanced antidirected trees

Let DD be an oriented graph on nn vertices, let δ0(D)\delta^0(D) denote its minimum semidegree, and let a balanced antidirected tree have equally many sources and sinks. The balanced-tree conjecture. Every oriented nn-vertex graph DD with δ0(D)>k/2\delta^0(D)>k/2 contains every balanced antidirected kk-edge tree whose total maximum degree is at most o(n)o(n). The conjecture concerns the threshold below the trivial greedy bound and remains open.

Sources & referencesView supporting material

Primary source

Maya Stein, “Oriented trees and paths in digraphs”, arXiv:2310.18719 (2024).

Additional references

2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2212.09876.

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.