摘要
图G的线性2-荫度,记作la_2(G),是使得图G能够被剖分成k个边不交森林的最小正整数k,其中每个森林的每棵树是长度至多为2的路.本文给出了可平面图和没有三角形的可平面图的线性2-荫度的新上界,即证明了:(1)对于一般可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+9;当△≡1,2(mod 4)时,1a_2(G)≤[△/2]+8;(2)对于不含三角形的可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+5;当△≡1,2(mod 4)时,la_2(G)≤[△/2]+6;其中△为图G的最大度.
Let G be a graph with maximum degree △ The linear 2-arboricity of G, denoted by la2（G）, is the least integer k such that G can be decomposed into k edge disjoint forests, whose component trees are paths of length at most 2. In this note, we show that （1） for general planar graphs, la2（G） ≤ [△/2]＋ 9 if△ ≡ 0, 3 （mod 4）, and la2（G） 〈 [△/2] ＋ 8 if△ ≡ 1,2 （mod 4）; （2） for triangle-free planar graphs, la2（G）≤[△/2]＋ 5 if A ≡0,3 （mod 4）, and la2（G） [△/2]＋ 6 if △≡ 1, 2 （mod 4）. These results improve known upper bounds of la2 （G） for general planar graphs and triangular- free planar graphs, respectively.
出处
《数学进展》
CSCD
北大核心
2016年第2期185-189,共5页
Advances in Mathematics（China）
基金
Supported by NSFC(No.11271335)
