The linear arboricity of planar graphs with maximum degree at least 5

被引：4

作者：

Chen, Hong-Yu ^{[2
]}

Qi, Jian-Ming ^{[1
]}

机构：

[1] Shanghai Dianji Univ, Dept Math & Phys, Shanghai 201306, Peoples R China

[2] Shanghai Inst Technol, Sch Sci, Shanghai 201418, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 20期

基金：

中国国家自然科学基金;

关键词：

Combinatorial problems; Planar graph; Linear arboricity; Cycle; PACKING;

D O I：

10.1016/j.ipl.2012.06.007

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let G be a planar graph with maximum degree Delta(G) >= 5. It is proved that la(G) = inverted right perpendicular Delta(G)/2inverted left perpendicular if G has no intersecting 4-cycles and intersecting 5-cycles. (c) 2012 Elsevier B.V. All rights reserved.

引用

页码：767 / 771

页数：5

共 18 条

[1]

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

[2] COVERING AND PACKING IN GRAPHS .4. LINEAR ARBORICITY [J].

AKIYAMA, J ;

EXOO, G ;

HARARY, F .

NETWORKS, 1981, 11 (01) :69-72

[3]

Bondy J. A., 1976, Graph theory with applications

[4]

Chen H.Y., GRAPHS COMB IN PRESS

[5]

Chen H.Y., UTIL MATH IN PRESS

[6] A Planar linear arboricity conjecture [J].

Cygan, Marek ;

Hou, Jian-Feng ;

Kowalik, Lukasz ;

Luzar, Borut ;

Wu, Jian-Liang .

JOURNAL OF GRAPH THEORY, 2012, 69 (04) :403-425

[7] THE LINEAR ARBORICITY OF SOME REGULAR GRAPHS [J].

ENOMOTO, H ;

PEROCHE, B .

JOURNAL OF GRAPH THEORY, 1984, 8 (02) :309-324

[8]

Gulden F., 1986, Mathematica Slovaca, V36, P225

[9] COVERING AND PACKING IN GRAPHS, .1. [J].

HARARY, F .

ANNALS OF THE NEW YORK ACADEMY OF SCIENCES, 1970, 175 (01) :198-&

[10]

Jianliang Wu, 2002, Journal of Systems Science and Complexity, V15, P372

← 1 2 →