A Planar linear arboricity conjecture |
| |
| Authors: | Marek Cygan Jian‐Feng Hou Łukasz Kowalik Borut Lužar Jian‐Liang Wu |
| |
| Affiliation: | 1. Institute of Informatics, University of Warsaw Banacha 2, , Poland;2. Center for Discrete Mathematics, Fuzhou University Fuzhou, , 350002 People's Republic of China;3. Institute of Mathematics, Physics, and Mechanics Jadranska 19, , Slovenia;4. School of Mathematics, Shandong University Jinan, , 250100 People's Republic of China |
| |
| 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 |
| |
| Keywords: | |
|
|
