2017/07/12 by Yang, Donglei, Bai, Yandong, Wang, Guanghui +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1707.03600
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