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 introduced the notion of list linear aboricity lla(G) of a graph G and conjectured that‘△(G)/2'≤la(G)=lla(G)≤‘△(G)+1/2' for any graph G.In this paper
we prove that la(G) = lla(G) =2 for any cubic graph G.
关键词
Keywords
references
Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:American Elsevier,1976.
Harary F.Covering and packing in graphsⅠ[J].Ann N Y Acad Sci,1970,175:198-205.
Akiyama J,Exoo G,Harary F.Covering and packing in graphsⅢ:Cyclic and acyclic invariants[J].Math Slovaca,1980, 30:405-417.
Wu J L.The linear arboricity of series-parallel graphs[J].Graphs Combin,2000,16:367-372.
Akiyama J,Exoo G,Harary F.Covering and packing in graphsⅣ:Linear arboricity[J].Networks,1981,11:69-72.
Enomoto H,Peroche B.The linear arboricity of some regular graphs[J].J Graph Theory,1984,8:309-324.
Guldan F.The linear arboricity of 10 regular graphs[J].Math Slovaca,1986,36:225-228.
京公网安备11010802024621