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-03-10
2016, Vol. 45(2): 185-189
DOI: 10.11845/sxjz.2014097b


PDF
[160 KB]
745
下载
842
浏览

引用导出
0
    /   /   推荐

摘要 图$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]. 数学进展, 2019, 48(2): 137-144.
[2] 卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155.
[3] 石慧苓, 高云澍. 标准多重图中点不交的重边四边形[J]. 数学进展, 2018, 47(3): 348-362.
[4] 卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372.
[5] 邓兴超, 宋贺, 苏贵福, 田润丽. 小直径二连通外平面图的彩虹连通数[J]. 数学进展, 2018, 47(3): 373-382.
[6] 田方. 一类稀疏随机图的距离匹配数[J]. 数学进展, 2018, 47(2): 175-188.
[7] 朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681.
[8] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.
[9] 单治超. 有限随机图上的随机游动和传染病模型[J]. 数学进展, 2017, 46(1): 1-12.
[10] 王力工, 孙丰妹. 单圈图的无符号拉普拉斯埃斯特拉达指数[J]. 数学进展, 2017, 46(1): 47-54.
[11] 冯荣权, 曾丽伟. 有向强正则图及其构造[J]. 数学进展, 2016, 45(6): 817-839.
[12] 崔淑玉,田贵贤. 图的各类矩阵表示的谱半径的界[J]. 数学进展, 2016, 45(5): 711-720.
[13] 李玉萍, 孟吉翔, 孙星红. 极大非正则图的边数[J]. 数学进展, 2016, 45(5): 721-726.
[14] 单治超. 有限图上首达时等随机变量的极限定理[J]. 数学进展, 2016, 45(4): 481-490.
[15] 李晓艳,陈敏,王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499.
Viewed
Full text


Abstract

Cited

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


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