不含4-圈的IC-平面图的线性荫度
Linear Arboricity of IC-Planar Graph Without 4-Cycles
DOI: 10.12677/AAM.2020.98142, PDF,  被引量 下载: 727  浏览: 1,080  科研立项经费支持
作者: 姜 楠, 黄丹君*：浙江师范大学数学与计算机科学学院，浙江 金华
关键词: IC-平面图；边分解；线性荫度；IC-Planar Graphs； Edge Partition； Linear Arboricity
摘要: 图G的边分解是指将G分解成子图G1, G2, . . . , Gm，使得E(G) = E(G1)∪ · · · ∪E(Gm)，且对任意i ≠ j，有E(Gi) ∩ E(Gj ) = ∅。若一个森林的每个连通分支都是路，则称该森林为线性森林。 图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m。本文利用权转移方法证明了不含4-圈且∆(G) ≥ 9的IC-平面图G的线性荫度为。
Abstract: An edge-partition of a graph G is a decomposition of G into subgraphs G1, G2, . . . , Gm such that E(G) = E(G1)∪ · · · ∪E(Gm) and E(Gi) ∩ E(Gj ) = ∅ for i ≠ j.  A linear forest is forest in which each connected component is a path. The linear arboricity la(G) is the least integer m such that G can be edge-partitioned into m linear forests. In this paper, we use the discharging method to study the linear arboricity la(G) of IC-planar graphs, and prove that la(G) = for each IC-planar graph G with ∆(G) ≥ 9 and without 4-cycles, where ∆(G) is the maximum degree of G.
文章引用：姜楠, 黄丹君. 不含4-圈的IC-平面图的线性荫度[J]. 应用数学进展, 2020, 9(8): 1213-1220. https://doi.org/10.12677/AAM.2020.98142

参考文献

[1] Harary, F. (1970) Covering and Packing in Graphs I. Annals of the New York Academy of Sciences, 175, 198-215.
[2] Akiyama, J., Exoo, G. and Harary, F. (1980) Covering and Packing in Graphs III: Cyclic and Acyclic Invariants. Mathematica Slovaca, 30, 405-417.
[3] Enomoto, H. and P´eroche, B. (1984) The Linear Arboricity of Some Regular Graphs. Journal of Graph Theory, 8, 309-324.
https://doi.org/10.1002/jgt.3190080211
[4] Guldan, F. (1986) The Linear Arboricity of 10-Regular Graphs. Mathematica Slovaca, 36, 225-228.
[5] Wu, J.L. and Wu, Y.W. (1999) On the Linear Arboricity of Planar Graphs. Journal of Graph Theory, 31, 129-134.
[6] Wu, J.L. and Wu, Y.W. (2008) The Linear Arboricity of Planar Graphs of Maximum Degree Seven Is Four. Journal of Graph Theory, 58, 210-220.
https://doi.org/10.1002/jgt.20305
[7] Wu, J.L., Hou, J.F. and Liu, G.Z. (2007) The Linear Arboricity of Planar Graphs with No Short Cycles. Progress in Theoretical Computer Science, 381, 230-233.
https://doi.org/10.1016/j.tcs.2007.05.003
[8] Chen, H.Y. and Qi, J.M. (2012) The Linear Arboricity of Planar Graphs with Maximum Degree at Least 5. Information Processing Letters, 112, 767-771.
https://doi.org/10.1016/j.ipl.2012.06.007
[9] Luo, C.Y. and Sun, L. (2019) The Linear Aboricity of Planar Graphs with 6-Cycles Containing at Most One Chord. Operations Research Transactions, 23, 113-119.
[10] Wu, J.L. (2000) On the Linear Arboricity of Series-Parallel Graphs. Graphs and Combinatorics, 16, 367-372.
https://doi.org/10.1007/s373-000-8299-9
[11] Zhang, X., Liu, G.Z. and Wu, J.L. (2011) On the Linear Arboricity of 1-Planar Graphs. Operations Research Transactions, 15, 38-44.
[12] Wang, H.X., Wu, J.L. and Chen, H.Y. (2014) On the Linear Arboricity of Graphs Embeddable in Surfaces. Information Processing Letters, 114, 475-479.
https://doi.org/10.1016/j.ipl.2014.03.013
[13] Wu, J.L., Hou, J.F. and Sun, X.Y. (2009) A Note on the Linear Arboricity of Planar Graphs without 4-Cycles. The Eighth International Symposium on Operations Research and Its Appli- cations, Zhangjiajie, 20-22 September 2009, 174-178.
[14] Wu, J.L. (2008) The Linear Arboricity of Graphs on Surfaces of Negative Euler Characteristic. SIAM Journal on Discrete Mathematics, 23, 54-58.
https://doi.org/10.1137/S0895480101394690

为你推荐