《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (11): 147-154.doi: 10.6040/j.issn.1671-9352.0.2022.221
杜红军(
),王慧娟*()
Hongjun DU(),Huijuan WANG*()
摘要：
线性荫度是一种非正常的边染色，图的线性荫度是指将它的边集划分为线性森林的最小数目。利用权转移方法，证明得到：对于任意的一个最大度Δ≥7的可嵌入到欧拉示性数非负的曲面图G而言，如果存在着两个固定的整数i, j∈{3, 4, 5, 6}，使得图G中不包含相邻的i-圈和j-圈，那么它的线性荫度是
中图分类号:
| 1 |
HARARY F . Covering and packing in graphs Ⅰ[J]. Annals of the New York Academy of Sciences, 1970, 175 (1): 198- 205.
doi: 10.1111/j.1749-6632.1970.tb56470.x |
| 2 | AKIYAMA J , EXOO G , HARARY F . Covering and packing in graphs Ⅲ: cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30, 405- 417. |
| 3 |
WU Jianliang . On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 1999, 31 (2): 129- 134.
doi: 10.1002/(SICI)1097-0118(199906)31:2<129::AID-JGT5>3.0.CO;2-A |
| 4 |
WU Jianliang , WU Yuwen . The linear arboricity of planar graphs of maximum degree seven is four[J]. Journal of Graph Theory, 2008, 58 (3): 210- 220.
doi: 10.1002/jgt.20305 |
| 5 | CYGAN M , HOU Jianfeng , KOWALIK Ł , et al. A planar linear arboricity conjecture[J]. Journal of Graph Theory, 2011, 69 (4): 403- 425. |
| 6 |
CHEN Hongyu , TAN Xiang , WU Jianliang , et al. The linear arboricity of planar graphs without 5-, 6-cycles with chords[J]. Graphs and Combinatorics, 2013, 29, 373- 385.
doi: 10.1007/s00373-011-1118-y |
| 7 |
CHEN Xianglian , WU Jianliang . The linear arboricity of planar graphs without 5-cycles with two chords[J]. Filomat, 2016, 30 (5): 1135- 1142.
doi: 10.2298/FIL1605135C |
| 8 | 罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23 (2): 113- 119. |
| LUO Zhaoyang , SUN Lin . The linear arboricity of planar graphs with 6-cycles containing at most one chord[J]. Operations Research Transactions, 2019, 23 (2): 113- 119. | |
| 9 | WANG Huijuan , LIU Bin , WU Jianliang . The linear arboricity of planar graphs without chordal short cycles[J]. Utilitas Mathematica, 2012, 87, 255- 263. |
| 10 |
WANG Huijuan , WU Lidong , WU Weili , et al. Minimum number of disjoint linear forests covering a planar graph[J]. Journal of Combinatorial Optimization, 2014, 28 (1): 274- 287.
doi: 10.1007/s10878-013-9680-2 |
| 11 | BONDY J A , MURTY U S R . Graph theory with applications[M]. London: Macmillan Press, 1979. |
| 12 |
WANG Huijuan , WU Jianliang , LIU Bin , et al. On the linear arboricity of graphs embeddable in surfaces[J]. Information Processing Letters, 2014, 114 (9): 475- 479.
doi: 10.1016/j.ipl.2014.03.013 |
| 13 | 陈洪玲, 王慧娟, 高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 山东大学学报(理学版), 2018, 53 (12): 17- 22. |
| CHEN Hongling , WANG Huijuan , GAO Hongwei . Linear arboricity of graphs embedded in a surface of non-negative Euler characteristic[J]. Journal of Shandong University(Natural Science), 2018, 53 (12): 17- 22. | |
| 14 | WU Jianliang , HOU Jianfeng , LIU Guizhen . The linear arboricity of planar graphs with no short cycles[J]. Theoretical Computer Science, 2007, 381, 230- 233. |
| 15 | WU Jianliang, HOU Jianfeng, SUN Xiangyong. A note on the linear arboricity of planar graphs without 4-cycles[C]//The Eighth International Symposium on Operations Research and its Applications (ISORA 2009). Beijing, China: World Publishing Corporation, 2009: 174-178. |
| [1] | 王淑娟,杨火根,柴莹. 过Bézier三边形测地线的有理多项式Coons曲面片重构[J]. 《山东大学学报(理学版)》, 2022, 57(6): 102-110. |
| [2] | 吴凤,张量. 关于常φ -曲率Sasaki统计流形的一些结果[J]. 《山东大学学报(理学版)》, 2021, 56(4): 86-93. |
| [3] | 陈洪玲,王慧娟,高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 《山东大学学报(理学版)》, 2018, 53(12): 17-22. |
| [4] | 刘华勇,谢新平,李璐,张大明,王焕宝. 一类满足G2连续的三角Bézier曲线曲面[J]. 山东大学学报（理学版）, 2016, 51(10): 65-71. |
| [5] | 徐常青1,安丽莎1,杜亚涛2. 平面图线性2-荫度的一个上界[J]. 山东大学学报（理学版）, 2014, 49(04): 38-40. |
| [6] | 金明浩1,2，裴东河1*. 三维Minkowski空间中具有逐点1型高斯映射的时间轴旋转曲面[J]. J4, 2013, 48(2): 57-61. |
| [7] | 王苒群,左连翠. 不含4-圈和5-圈的平面图的线性2-荫度[J]. J4, 2012, 47(6): 71-75. |
| [8] | 王 文,马学强,刘 弘 . 分形几何在计算机辅助玻璃幕墙概念设计中的应用[J]. J4, 2008, 43(11): 31-35 . |
|
