List linear arboricity of planar graphs
List linear arboricity of planar graphs
复制标题
DOI：
10.7151/dmgt.1460
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Xinhui An;Baoyindureng Wu
中科院分区：
文献类型：
--
作者：
Xinhui An;Baoyindureng Wu
图G的线性荫度la（G）等于将其边分解为k个边不交的线性森林的最小整数k. An和Wu引入了图G的表线性荫度lla（G）的概念，并猜想对任意图G，lla（G）= lla（G）.我们证明了这个猜想对任意大于13的平面图成立，或者对任意大于7且没有i-圈的平面图成立，其中i-圈的个数为2f 3; 4; 5g.证明了对于任意大于9的平面图，d（G）2 e6 lla（G）6d（G）+12e.
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We conrm that this conjecture is true for any planar graph having > 13, or for any planar graph with > 7 and without i-cycles for some i 2 f3; 4; 5g. We also prove that d ( G) 2 e 6 lla(G) 6 d ( G)+1 2 e for any planar graph having > 9.