Please wait a minute...
北京大学期刊网 | 作者  审稿人  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2016, Vol. 45(2): 185-189
研究论文
可平面图的线性2-荫度的新上限
Improved Upper Bound of Linear 2-arboricity of Planar Graphs

景昱波,王应前
JING Yubo, WANG Yingqian

浙江师范大学数理与信息工程学院, 金华, 浙江, 321004
College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, P. R. China

收稿日期: 2014-06-17
2016, Vol. 45(2): 185-189
DOI: 10.11845/sxjz.2014097b


PDF
[160 KB]
709
下载
578
浏览

引用导出
E-mail这篇文章
E-mail提醒
RSS订阅

摘要 图$G$的线性2-荫度, 记作$\mathrm{la}_2(G)$, 是使得图$G$能够被剖分成$k$个边不交森林的最小正整数$k$, 其中每个森林的每棵树是长度至多为2的路. 本文给出了可平面图和没有三角形的可平面图的线性2-荫度的新上界, 即证明了:(1) 对于一般可平面图, 当$\Delta \equiv 0,3$ (mod 4)时, $\mathrm{la}_{2}(G) \leq \lceil \frac{\Delta}{2} \rceil + 9$; 当$\Delta \equiv 1,2$ (mod 4)时, $\mathrm{la}_{2}(G) \leq \lceil \frac{\Delta}{2} \rceil + 8$; (2) 对于不含三角形的可平面图, 当$\Delta \equiv 0,3$ (mod 4)时, $\mathrm{la}_{2}(G) \leq \lceil \frac{\Delta}{2} \rceil + 5$; 当$\Delta \equiv 1,2$ (mod 4)时, $\mathrm{la}_{2}(G) \leq \lceil \frac{\Delta}{2} \rceil + 6$;其中$\Delta$为图$G$的最大度.
Abstract:Let $G$ be a graph with maximum degree $\Delta$. The linear 2-arboricity of $G$, denoted by $\mathrm{la}_{2}(G)$, is the least integer $k$ such that $G$ can be decomposed into $k$ edge disjoint forests, whose component trees are paths of length at most 2. In this note, we show that (1) for general planar graphs, $\mathrm{la}_{2}(G) \leq \lceil \frac{\Delta}{2} \rceil + 9$ if $\Delta \equiv 0,3$ (mod 4), and $\mathrm{la}_{2}(G) \leq \lceil \frac{\Delta}{2} \rceil + 8$ if $\Delta \equiv 1,2$ (mod 4)|(2) for triangle-free planar graphs, $\mathrm{la}_{2}(G) \leq \lceil\frac{\Delta}{2} \rceil + 5$ if $\Delta \equiv 0,3$ (mod 4), and $\mathrm{la}_{2}(G) \leq \lceil \frac{\Delta}{2} \rceil + 6$ if $\Delta \equiv 1,2$ (mod 4).\\These results improve known upper bounds of $\mathrm{la}_{2}(G)$ for general planar graphs and triangular-free planar graphs, respectively.
PACS:  O157.5  
[1] Akiyama, J., Three developing topics in graph theory, Doctoral Dissertation, Tokyo: University of Tokyo, 1980.
[2] Akiyama, J., Exoo, G. and Harary, F., Covering and packing in graphs III: cyclic and acyclic invariants, Math. Slovaca,1980, 30(4): 405-417.
[3] Aldred, R.E.L. and Wormald, N.C., More on the linear $k$-arboricity of regular graphs, Australas. J. Combin., 1998, 18: 97-104.
[4] Bermond, J.C., Fouquet, J.L., Habib, M. and Péroche, B., On linear $k$-arboricity, Discrete Math., 1984, 52(2/3): 123-132.
[5] Borodin, O.V., On the total coloring of planar graphs, J. Reine Angew. Math., 1989, 394: 180-185.
[6] Chen, B.L., Fu, H.L. and Huang, K.C., Decomposing graphs into forests of paths with size less than three, Australas. J. Combin.,
1991, 3: 55-73.
[7] Chen, H.Y., Tan, X. and Wu, J.L., The linear 2-arboricity of planar graphs without adjacent short cycles, Bull. Korean Math. Soc., 2012, 49(1): 145-154.
[8] Enomoto, H. and Péroche, B., The linear arboricity of some regular graphs, J. Graph Theory, 1994, 8(2): 309-324.
[9] Guldan, F., The linear arboricity of 10 regular graphs, Math. Slovaca, 1986, 36(3): 225-228.
[10] Habib, M. and Péroche, B., Some problems about linear arboricity, Discrete Math., 1982, 41(2): 219-220.
[11] Lih, K.W., Tong, L.D. and Wang, W.F., The linear 2-arboricity of outerplanar graphs, Ars Combin., 2004, 73: 13-22.
[12] Vizing, V.G., Critical graphs with given chromatic class, Metody Diskret. Analiz., 1965, 5: 9-17 (in Russian).
[13] Wu, J.L., On the linear arboricity of planar graphs, J. Graph Theory, 1999, 31(2): 129-134.
[1] 周倩楠, 王力工, 卢勇. 关于哈密顿图和可迹图的一些充分条件[J]. 数学进展, 2018, 47(1): 31-40.
[2] 文飞, 黄琼湘, 马小玲. 一类图的谱半径与特征多项式[J]. 数学进展, 2018, 47(1): 41-50.
[3] 李建喜, 常安. 图的规范拉普拉斯特征值的上界[J]. 数学进展, 2018, 47(1): 51-55.
[4] 潘文华, 徐常青. 无$K_4$-图子式的图的邻和可区别边染色[J]. 数学进展, 2017, 46(6): 839-847.
[5] 刘颖, 沈建. 关于图的规范拉普拉斯特征值和的若干结果[J]. 数学进展, 2017, 46(6): 848-856.
[6] 朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681.
[7] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.
[8] 单治超. 有限随机图上的随机游动和传染病模型[J]. 数学进展, 2017, 46(1): 1-12.
[9] 王力工, 孙丰妹. 单圈图的无符号拉普拉斯埃斯特拉达指数[J]. 数学进展, 2017, 46(1): 47-54.
[10] 冯荣权, 曾丽伟. 有向强正则图及其构造[J]. 数学进展, 2016, 45(6): 817-839.
[11] 崔淑玉,田贵贤. 图的各类矩阵表示的谱半径的界[J]. 数学进展, 2016, 45(5): 711-720.
[12] 李玉萍, 孟吉翔, 孙星红. 极大非正则图的边数[J]. 数学进展, 2016, 45(5): 721-726.
[13] 单治超. 有限图上首达时等随机变量的极限定理[J]. 数学进展, 2016, 45(4): 481-490.
[14] 李晓艳,陈敏,王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499.
[15] 姚京京, 邵泽玲, 徐常青. \mbox{\boldmath $\Delta=3$} 的图的邻和可区别全可选性[J]. 数学进展, 2016, 45(3): 343-348.
Viewed
Full text


Abstract

Cited

  Discussed   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .