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.
References:
[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.,
Send comments to dan.archdeacon@uvm.edu
November 2003