Search

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. In 1981, Akiyama, Exoo and Harary conjectured that ⌈Δ(G)/2⌉ ≤ la(G) ≤ ⌈Δ(G)+1/2 ⌉ for any simple graph G. A graph G is 1-planar if it can be drawn in the plane so that each edge has at most one crossing. In this paper, we confirm the conjecture for 1-planar graphs G with Δ(G) ≥ 13. [ABSTRACT FROM AUTHOR]