Journal of East China Normal University(Natural Sc ›› 2013, Vol. 2013 ›› Issue (1): 7-10, 23.

• Article • Previous Articles     Next Articles

Linear arboricity of an embedded graph on a surface of large genus

LV Chang-qing,  FANG Yong-lei   

  1. School of Mathematics and Statistics, Zaozhuang University, Zaozhuang Shandong 277160, China
  • Received:2012-04-01 Revised:2012-07-01 Online:2013-01-25 Published:2013-01-18

Abstract: The linear arboricity of a graph G is the minimum number
of linear forests which partition the edges of G. This paper
proved that if G can be embedded on a surface of large genus
without 4-cycle and Δ(G)(4545ε+10),
then its linear arboricity is Δ2, where
ε=22h if the orientable surface with genus
\,h(h>1)\,or ε=2k if the nonorientable surface with
genus \,k(k>2). It improves the bound obtained by J. L. Wu. As an
application, the linear arboricity of a graph with fewer edges were
concluded.

Key words: linear arboricity, surface, embedded graph, Euler characteristic

CLC Number: