Linear Arboricity of Regular Digraphs

作     者：Wei Hua HE Hao LI Yan Dong BAI Qiang SUN 

作者机构：Department of Applied MathematicsGuangdong University of TechnologyGuangzhou 510006P.R.China Laboratoire de Recherche en InformatiqueUMR 8623C.N.R.S.-Universitg de Paris-sud91405-Orsay cedexFrance 

出 版 物：《Acta Mathematica Sinica,English Series》 (数学学报（英文版）)

年 卷 期：2017年第33卷第4期

页      面：501-508页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Supported by NSFC(Grant Nos.11601093 and 11671296) 

主　　题：Linear arboricity digraph Lovász Local Lemma random regular digraphs 

摘      要：A linear directed forest is a directed graph in which every component is a directed *** linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.