The Linear 2-Arboricity of Planar Graphs
The Linear 2-Arboricity of Planar Graphs
复制标题
DOI：
10.1007/s00373-002-0504-x
复制
发表时间：
2003-06
影响因子：
0.7
通讯作者：
Ko-Wei Lih;Li-Da Tong;Weifan Wang
中科院分区：
文献类型：
--
作者：
Ko-Wei Lih;Li-Da Tong;Weifan Wang
画一个最大度数Δ和周长的平面图形。gis的线性2-树性(G)是最小的整数，使得G可以被划分成不相交的森林，这些森林的成分树是长度最多为2的路径。证明了(1)la2(G)≤（Δ+1）/2²+12；(2)水(G)≤⌈(Δ+ 1)/ 2⌉+ 6 ifg≥4;(3)水(G)≤⌈(Δ+ 1)/ 2⌉+ 2 ifg≥5;(4)水(G)≤⌈(Δ+ 1)/ 2⌉+ 1 ifg≥7。
LetGbe a planar graph with maximum degree Δ and girthg. The linear 2-arboricityla2(G) ofGis the least integerksuch thatGcan be partitioned intokedge-disjoint forests, whose component trees are paths of length at most 2. We prove that (1)la2(G)≤⌈(Δ+1)/2⌉+12; (2)la2(G)≤⌈(Δ+1)/2⌉+6 ifg≥4; (3)la2(G)≤⌈(Δ+1)/2⌉+2 ifg≥5; (4)la2(G)≤⌈(Δ+1)/2⌉+1 ifg≥7.