Partitioning digraphs with outdegree at least 4
Partitioning digraphs with outdegree at least 4
复制标题
DOI：
10.1002/jgt.22715
复制
发表时间：
2020-06
影响因子：
0.9
通讯作者：
Guanwu Liu;Xingxing Yu
中科院分区：
文献类型：
--
作者：
Guanwu Liu;Xingxing Yu
Scott提出了一个确定cd的问题，使得如果D是一个有m条弧的有向图，且最小出度d ≥ 2，则V（D）有一个划分V1，V2，使得min { e（V1，V2），e（V2，V1）} ≥ cdm，其中e（V1，V2）（分别为e（V2，V1））是从V1到V2（分别为从V2到V1）的弧数。Lee、洛和Sudakov证明了c 2 = 1 scin 6 + o（1）和c 3 = 1 scin 5 + o（1），并证明了当d ≥ 4时，c d = d − 1 2（2 d − 1）+ o（1）。本文证明了c4 = 3scin 14 + o（1），并证明了d ≥ 5时的部分结果.
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 .