An Improved Upper Bound on the Linear 2-arboricity of 1-planar Graphs

被引：4

作者：

Liu, Juan ^{[1
]}

Wang, Yi Qiao ^{[2
]}

Wang, Ping ^{[3
]}

Zhang, Lu ^{[1
]}

Wang, Wei Fan ^{[1
]}

机构：

[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China

[2] Beijing Univ Chinese Med, Sch Management, Beijing 100029, Peoples R China

[3] St Francis Xavier Univ, Dept Math & Stat, Antigonish, NS, Canada

来源：

ACTA MATHEMATICA SINICA-ENGLISH SERIES | 2021年 / 37卷 / 02期

关键词：

1-planar graph; linear; 2-arboricity; edge-partition; maximum degree;

D O I：

10.1007/s10114-020-9488-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The linear 2-arboricity la(2)(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. In this paper, we prove that if G is a 1-planar graph with maximum degree Delta, then la(2)(G) <= [Delta+1/2]+7. This improves a known result of Liu et al. (2019) that every 1-planar graph G has la(2)(G)<= [Delta+1/2] +14. We also observe that there exists a 7-regular 1-planar graph G such that la(2)(G)=6= [Delta+1/2]+2, which implies that our solution is within 6 from optimal.

引用

页码：262 / 278

页数：17

共 18 条

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

BERMOND, JC ;

FOUQUET, JL ;

HABIB, M ;

PEROCHE, B .

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

[2] Acyclic colouring of 1-planar graphs [J].

Borodin, OV ;

Kostochka, AV ;

Raspaud, A ;

Sopena, E .

DISCRETE APPLIED MATHEMATICS, 2001, 114 (1-3) :29-41

[3] A NEW PROOF OF THE 6 COLOR THEOREM [J].

BORODIN, OV .

JOURNAL OF GRAPH THEORY, 1995, 19 (04) :507-521

[4] Linear k-arboricities on trees [J].

Chang, GJ ;

Chen, BL ;

Fu, HL ;

Huang, KC .

DISCRETE APPLIED MATHEMATICS, 2000, 103 (1-3) :281-287

[5]

Chen B.-L., 1991, AUSTRALAS J COMBIN, V3, P55

[6] On the linear k-arboricity of Kn and Kn,n [J].

Chen, BL ;

Huang, KC .

DISCRETE MATHEMATICS, 2002, 254 (1-3) :51-61

[7] The structure of 1-planar graphs [J].

Fabrici, Igor ;

Madaras, Tomas .

DISCRETE MATHEMATICS, 2007, 307 (7-8) :854-865

[8]

FU HL, 1994, ARS COMBINATORIA, V38, P309

[9] The linear 2-arboricity of planar graphs [J].

Lih, KW ;

Tong, LD ;

Wang, WF .

GRAPHS AND COMBINATORICS, 2003, 19 (02) :241-248

[10] Light structures in 1-planar graphs with an application to linear 2-arboricity [J].

Liu, Juan ;

Hu, Xiaoxue ;

Wang, Weifan ;

Wang, Yiqiao .

DISCRETE APPLIED MATHEMATICS, 2019, 267 :120-130

← 1 2 →