不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ'(G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为△/2]+4.

An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles

An edge-partition of a graph G is a decomposition of G into subgraphs G₁, G₂,…, G_m such that E(G)=E(G₁)∪ E(G₂)∪…∪ E(G_m) and E(G_i)∩ E(G_j)=∅ for i≠j. A linear k-forest is a graph in which each component is a path of length at most k. The linear k-arboricity la_k(G) of a graph G is the least integer m such that G can be edge-partitioned into m linear k-forests. For extremities, la₁(G) is the edge chromatic number χ'(G) of G; la_∞(G) representing the case when component paths have unlimited lengths is the ordinary linear arboricity la(G) of G. In this paper, we use the discharging method to study the linear 2-arboricity la₂(G) of planar graphs. Let G be a planar graph with neither 5-cycles nor adjacent 4-cycles. We prove that if G is connected and δ(G) ≥ 2, then G contains an edge xy with d(x)+d(y) ≤ 8 or a 2-alternating cycle. By this result, we obtain the upper bound of the linear 2-arboricity of G is ?△/2?+4.