On splitting digraphs. (June 2018) - Yang, Donglei; Bai, Yandong; Wang, Guanghui; Wu, Jianliang
Abstract: In 1995, Stiebitz asked the following question: For any positive integers s, t, is there a finite integer f ( s, t ) such that every digraph D with minimum out-degree at least f ( s, t ) admits a bipartition ( A, B ) such that A induces a subdigraph with minimum out-degree at least s and B induces a subdigraph with minimum out-degree at least t ? We give an affirmative answer for tournaments, multipartite tournaments, and digraphs with bounded maximum in-degrees. In particular, we show that for every ϵ with 0 < ϵ < 1 ∕ 2, there exists an integer δ 0 such that every tournament with minimum out-degree at least δ 0 admits a bisection ( A, B ), so that each vertex has at least ( 1 ∕ 2 − ϵ ) of its out-neighbors in A, and in B as well.