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 $\Delta(G)\geq (\sqrt{45-45\varepsilon}+10)$,
then its linear arboricity is $\lceil \frac{\Delta}{2}\rceil$, where
$\varepsilon=2-2h$ if the orientable surface with genus
\,$h(h>1)$\,or $\varepsilon=2-k$ 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: