A Planar linear arboricity conjecture
Marek Cygan, Jian‐Feng Hou, Łukasz Kowalik, Borut Lužar, Jian‐Liang Wu · Journal of Graph Theory · 2011
Abstract The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ⌈Δ/2⌉ or ⌈(Δ + 1)/2⌉. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ⌈Δ/2⌉. We conjecture that for planar graphs, this equality is true also for any even Δ⩾6. In this article we show that it is true for any even Δ⩾10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ⩾9. © 2010 Wiley Periodicals, Inc. J Graph Theory