|
|
- 2018
可嵌入到欧拉示性数非负的曲面图的线性荫度
|
Abstract:
摘要： 图G的线性荫度是一种非正常的边染色,即它的边集合E(G)可以分割成线性森林的最小数量,用la(G)表示。主要研究最大度Δ(G)≥7且可嵌入到欧拉示性数非负曲面图G上的线性荫度,证明了如果图G中不含相邻的含弦6-圈,则图G的线性荫度为「Δ/2。
Abstract: The linear arboricity of graph G, denoted by la(G), is the minimum number of linear forest required to partition the edge set E(G), which is an improper edge coloring. The linear arboricity of graph which can be embedded in a surface of non-negative Euler characteristic with maximum Δ(G)≥7 is mainly studied. If there is no adjacent chordal 6-cycle, then the arboricity of graph G is「Δ/2
| [1] | GULDAN F. The linear arboricity of 10 regular graph[J]. Mathematical Institute of the Slovak Academy of Sciences, 1986, 36(3):225-228. |
| [2] | WU Jianliang, WU Yuwen. The linear arboricity of planar graphs of maximum degree seven are four[J]. Journal of Graph Theory, 2008, 58(3):210-220. |
| [3] | FRANK H. Covering and packing in graphs, I.[J]. Annals of the New York Academy of Sciences, 2010, 175(1):198-205. |
| [4] | WU J L, LIU G, WU Y W. The linear arboricity of composition graphs[J]. Journal of Systems Science & Complexity, 2002, 15(4):38-41. |
| [5] | WU Jianling. The linear arboricity of Series-Parallel graphs[J]. Graphs & Combinatorics, 2000, 16(3):367-372. |
| [6] | JIN A, EXOO G, HARARY F. Covering and packing in graphs IV: linear arboricity[J]. Networks, 2010, 11(1):69-72. |
| [7] | WU Jianliang, HOU Jianfeng, SUN Xiangyong. A note on the linear arboricity of planar graphs without 4-cycles[J]. The Eighth International Symposium on Operations Research and Its Applications, 2009, 09:174-178. |
| [8] | AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs III: cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30(4):405-417. |
| [9] | ENMOTO H, PEROCHE B. The linear arboricity of some regular graphs[J]. Journal of Graph Theory, 1984, 8(2):309-324. |
| [10] | CYGAN M, HOU J, KOWALIK L, et al. A planar linear arboricity conjecture[J]. Journal of Graph Theory, 2012, 69(4):403-425. |
| [11] | 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. |
| [12] | ALON N. The linear arboricity of graphs[J]. Israel Journal of Mathematics, 1988, 62(3):311-325. |
| [13] | WU Jianliang. On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 1999, 31(2):129-134. |
