On splitting digraphs. (June 2018)

• Record Type: Journal Article
• Authors: Yang, Donglei; Bai, Yandong; Wang, Guanghui; Wu, Jianliang
• Is Part Of: European journal of combinatorics. Volume 71(2018)
• Page Start: 174
• Page End: 179
• Publication Date: 2018-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.03.005
• Languages: English
• ISSNs: 0195-6698

Abstract

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.