平面图线性2-荫度的一个上界

An upper bound on the linear 2-arboricity of planar graph

设图G为最大度为Δ的平面图。图G的线性2-荫度是将图G的边集合分解成k个线性森林的最小整数k,其中每个分支树为长至多为2的路,记为la2(G)。得到了平面图线性2-荫度的上界:若Δ≡0,3(mod 4),则la2(G)≤「Δ/2?+8;若Δ≡1,2(mod 4),则la2(G)≤「Δ/2?+7。

Let G be a planar graph with maximum degreeΔ.The linear 2-arboricity of G is the least integer k such that G can be partitioned into k edge disjoint forests, whose component trees are paths of length at most 2.It is denoted by la2（G）.We get that la2（G）≤「Δ/ 2 ＋8 ifΔ≡0,3（mod 4） and la2（G）≤「Δ/2 ＋7 ifΔ≡1,2（mod 4）.