Linear arboricity and linear k-arboricity of regular graphs

被引：32

作者：

Alon, N ^{[1
]}

Teague, VJ

Wormald, NC

机构：

[1] Inst Adv Study, Sch Math, Princeton, NJ 08540 USA

[2] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, IL-69978 Tel Aviv, Israel

[3] Univ Melbourne, Dept Math & Stat, Parkville, Vic 3052, Australia

来源：

GRAPHS AND COMBINATORICS | 2001年 / 17卷 / 01期

关键词：

Regular Graph; Probabilistic Argument; Linear Arboricity;

D O I：

10.1007/PL00007233

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We find upper bounds on the linear k-arboricity of d-regular graphs using a probabilistic argument. For small ii these bounds are new. For large k they blend into the known upper bounds on the linear arboricity of regular graphs.

引用

页码：11 / 16

页数：6

共 7 条

[1]

Akiyama J., 1980, Mathematica Slovaca, V30, P405

[2]

Aldred R. E. L., 1998, AUSTRALAS J COMBIN, V18, P97

[3] THE LINEAR ARBORICITY OF GRAPHS [J].

ALON, N .

ISRAEL JOURNAL OF MATHEMATICS, 1988, 62 (03) :311-325

[4]

ALON N, 1992, PROBABILISTIC METHOD

[5] ON LINEAR K-ARBORICITY [J].

BERMOND, JC ;

FOUQUET, JL ;

HABIB, M ;

PEROCHE, B .

DISCRETE MATHEMATICS, 1984, 52 (2-3) :123-132

[6]

BONDY JA, 1988, J LON MATH SOC H, V37, P14

[7] Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5 [J].

Thomassen, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (01) :100-109

← 1 →