THE LINEAR ARBORICITY OF GRAPHS ON SURFACES OF NEGATIVE EULER CHARACTERISTIC

摘要

The linear arboricity of a graph G is the minimum number of linear forests which partition the edges of G. In the present, it is proved that if a graph G can be embedded in a surface of Euler characteristic ε ＜ 0 and Δ(G) ≥ (46 - 54ε)~(1/2) + 19, then its linear arboricity is [Δ(G)/2]. Some related results on the girth and maximum average degree are also obtained.