Premium
Partitioning digraphs with outdegree at least 4
Author(s) -
Liu Guanwu,
Yu Xingxing
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22715
Subject(s) - digraph , partition (number theory) , combinatorics , mathematics , discrete mathematics
Abstract Scott asked the question of determining c d such that if D is a digraph with m arcs and minimum outdegree d ≥ 2 then V ( D ) has a partition V 1 , V 2 such that min { e ( V 1 , V 2 ) , e ( V 2 , V 1 ) } ≥ c d m , where e ( V 1 , V 2 ) (respectively, e ( V 2 , V 1 ) ) is the number of arcs from V 1 to V 2 (respectively, from V 2 to V 1 ). Lee, Loh, and Sudakov showed that c 2 = 1 ∕ 6 + o ( 1 ) and c 3 = 1 ∕ 5 + o ( 1 ) , and conjectured that c d = d − 1 2 ( 2 d − 1 )+ o ( 1 ) for d ≥ 4 . In this paper, we show c 4 = 3 ∕ 14 + o ( 1 ) and prove some partial results for d ≥ 5 .