不含4-圈的IC-平面图的线性荫度  

Linear Arboricity of IC-Planar Graph Without 4-Cycles

作　　者：姜楠 黄丹君 

机构地区：[1]浙江师范大学数学与计算机科学学院,浙江 金华

出　　处：《应用数学进展》2020年第8期1213-1220,共8页Advances in Applied Mathematics

摘　　要：图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的线性荫度为。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.

关 键 词：IC-平面图 边分解 线性荫度 

分 类 号：O15[理学—数学]