A Note on The Linear Arboricity of Planar Graphs without 4-Cycles∗
Jianliang Wu, Jianfeng Hou, Xiang-Yong Sun · 2009
Abstract The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, it is proved that if G is a planar graph with ∆(G) ≥ 5 and without 4-cycles, then la(G) = ⌈ ∆(G) 2 ⌉. Moreover, the bound that ∆(G) ≥ 5 is sharp.