Minimum-semidegree conjecture for balanced antidirected trees

At least 3 years old · documented by

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.

References

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.