Linear Arboricity of Regular Digraphs

被引：0

作者：

Wei Hua HE ^{[1
]}

Hao LI ^{[2
]}

Yan Dong BAI ^{[2
]}

Qiang SUN ^{[2
]}

机构：

[1] Department of Applied Mathematics, Guangdong University of Technology

[2] Laboratoire de Recherche en Informatique,UMR 8623,C.N.R.S.-Université de Paris-sud

来源：

Acta Mathematica Sinica,English Series | 2017年 / 04期

关键词：

Linear arboricity; digraph; Lovász Local Lemma; random regular digraphs;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

A linear directed forest is a directed graph in which every component is a directed path.The 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.

引用

页码：501 / 508

页数：8