The Linear Arboricity of Planar Graphs

The linear arboricity of a graph G is defined as the minimum number of paths which together partition the edges of G. (In contrast, the ordinary arboricity is the minimum number of forests which partition the edges.) It is equivalent to coloring the edges of a graph so that each color class is an acyclic graph. . Akiyama, Exoo and Harary conjecture that the linear arboricity of a graph with maximum degree D is at least ceiling[D/2] and at most  ceiling[D+1)/2], where ceiling is the `round-up' function. To the proposer's knowledge, the problem is still open.

Wu [W] proved that the conjecture was true for all planar graphs of maximum degree not equal to 7. Moreover, if G is a planar graph of maximum degree D and girth g, then the lower bound is achieved provided (1) D is at least 13 and g is at least 3, (2) D is at least 7 and g is at least 4, (3) D is at least 5 and g is at least 5, or (4) D is at least 3 and g is at least 6.

Problem: Find the linear arboricity of planar graphs.


[AEH] J. Akiyama, G. Exoo, and F. Harary, Covering and packing in graphs III: cyclic and acyclic invariants, Math. Slovaca 30 (1980) 405-417.

[W] Jian-Liang Wu, On the linear arboricity of planar graphs, preprint

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to

November 2003