期刊文献+

不含4-圈的平面图的线性2-荫度 被引量:4

The linear 2-arboricity of planar graphs without 4-cycles
下载PDF
导出
摘要 图G的线性2-荫度la2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树是长度至多为2的路.证明了:若G为不含4-圈的平面图,则la2(G)≤「Δ(G)+12﹁+3,其中Δ(G)表示图G的点最大度. The linear 2-arboricity ια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. It was proved that ια2(G)≤[△(G)+1/2]+3 if G is a planar graph without 4-ycles.
作者 钱景 王维凡
出处 《浙江师范大学学报(自然科学版)》 CAS 2006年第2期121-125,共5页 Journal of Zhejiang Normal University:Natural Sciences
基金 国家自然科学基金资助项目(10471131) 浙江省自然科学基金资助项目(M103094Y604167)
关键词 图论 线性荫度 线性2-荫度 森林 边分解 graph theory linear arboricity linear 2-arboricity forest edge-decomposition
  • 相关文献

参考文献13

  • 1邦迪JA 默蒂USR.图论及其应用[M].北京:科学出版社,1984..
  • 2Habib M,PEroche P. Some problems about linear arboricity[J]. Discrete Math,1982,41(2):219-220.
  • 3Bermond J C,Fouquet J L,Habib M,et aL. On linear k-arboricity[J]. Discrete Math,1984,52(2/3):123-132.
  • 4Jackson B,Wormald N C. On the linear k-arboricity of cubic graphs[J]. Discrete Math, 1996,162( 1/3):293-297.
  • 5Aldred R E L,Wormald N C. More on the linear k-arboricity of regular graphs[J]. Australas J Combin,1998,18(1):97-104.
  • 6Chen Bailiang, Fu Henglin, Huang Guoqing. Decomposing graphs into forests of paths with size less than three[J]. Australas J Combin, 1991,3(1) : 55-73.
  • 7Fu Henglin,Huang Guoqing. The linear 2-arboricity oF complete bipartite graphs[J]. Ars Combin, 1994,38(3):309-318.
  • 8Thomassen C. Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5[J]. J Combin Theory Ser B,1999,75(1) :100-109.
  • 9Zhang Zhenhua. Algorithmic aspects of linear k-arboricity[J]. Taiwan Residents J Math, 1999,3(1) :73-81.
  • 10Zhang Zhenhua, Chen Bailiang, Fu Henglin, et al. Linear k-arboricities on trees[J]. Discrete Appl Math, 2000,103(1/3):281-287.

共引文献39

同被引文献7

引证文献4

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部