可平面图的线性2-荫度的新上限

摘要

图G的线性2-荫度,记作la2(G),是使得图G能够被剖分成k个边不交森林的最小正整数k,其中每个森林的每棵树是长度至多为2的路.本文给出了可平面图和没有三角形的可平面图的线性2-荫度的新上界,即证明了:(1)对于一般可平面图,当Δ≡0,3 (mod 4)时,la2(G)≤([)Δ/2(])+9;当Δ三1,2 (mod 4)时,la2(G)≤([)Δ/2(])+8;(2)对于不含三角形的可平面图,当Δ三0,3 (mod 4)时,la2(G)≤([)Δ/2(])+5;当Δ≡1,2(mod 4)时,la2(G)≤([)Δ/2(])+6;其中Δ为图G的最大度.