Lee, Loh, and Sudakov's conjecture on judicious bipartitions of digraphs
Lee, Loh, and Sudakov's conjecture on judicious bipartitions of digraphs
Let be a digraph with arcs and minimum outdegree at least an integer . For a bipartition , write for the number of arcs directed from to . Lee, Loh, and Sudakov's conjecture. Every such digraph admits a bipartition with
This conjecture addresses Scott's question about the largest constant guaranteeing a balanced directed cut in digraphs with prescribed minimum outdegree. The supplied source does not state whether the conjecture has been resolved.
Sources & referencesView supporting material
Primary source
Jianfeng Hou, Huawen Ma, Xingxing Yu and Xia Zhang, “A bound on judicious bipartitions of directed graphs”, arXiv:1805.05506 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.