The linear 2-arboricity of planar graphs

被引:44
作者
Lih, KW [1 ]
Tong, LD
Wang, WF
机构
[1] Acad Sinica, Inst Math, Taipei 115, Taiwan
[2] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 804, Taiwan
[3] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China
关键词
D O I
10.1007/s00373-002-0504-x
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a planar graph with maximum degree Delta and girth g. The linear 2-arboricity la(2)(G) of 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. We prove that (1) la(2)(G)less than or equal toinverted right perpendicular(Delta+1)/2inverted left perpendicular+12; (2) la(2)(G)less than or equal toinverted right perpendicular(Delta+1)/2inverted left perpendicular+6 if ggreater than or equal to4; (3) la(2)(G)less than or equal toinverted right perpendicular(Delta+1)/2inverted left perpendicular+2 if ggreater than or equal to5; (4) la(2)(G)less than or equal toinverted right perpendicular(Delta+1)/2inverted left perpendicular+1 if ggreater than or equal to7.
引用
收藏
页码:241 / 248
页数:8
相关论文
共 18 条
[1]  
Akiyama J., 1980, Mathematica Slovaca, V30, P405
[2]  
Akiyama J., 1980, THESIS U TOKYO
[3]  
Aldred R. E. L., 1998, AUSTRALAS J COMBIN, V18, P97
[4]   ON LINEAR K-ARBORICITY [J].
BERMOND, JC ;
FOUQUET, JL ;
HABIB, M ;
PEROCHE, B .
DISCRETE MATHEMATICS, 1984, 52 (2-3) :123-132
[5]   List edge and list total colourings of multigraphs [J].
Borodin, OV ;
Kostochka, AV ;
Woodall, DR .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 71 (02) :184-204
[6]  
BORODIN OV, 1989, J REINE ANGEW MATH, V394, P180
[7]  
Chang GJ, 1999, TAIWAN J MATH, V3, P73
[8]   Linear k-arboricities on trees [J].
Chang, GJ ;
Chen, BL ;
Fu, HL ;
Huang, KC .
DISCRETE APPLIED MATHEMATICS, 2000, 103 (1-3) :281-287
[9]  
Chen B., 1991, AUSTRALAS J COMBIN, V3, P55
[10]   THE LINEAR ARBORICITY OF SOME REGULAR GRAPHS [J].
ENOMOTO, H ;
PEROCHE, B .
JOURNAL OF GRAPH THEORY, 1984, 8 (02) :309-324