华东师范大学学报(自然科学版) ›› 2013, Vol. 2013 ›› Issue (1): 7-10, 23.

• 应用数学与基础数学 • 上一篇    下一篇

较大亏格曲面嵌入图的线性荫度

吕长青, 房永磊   

  1. 枣庄学院~~数学与统计学院, 山东~~枣庄 277160
  • 收稿日期:2012-04-01 修回日期:2012-07-01 出版日期:2013-01-25 发布日期:2013-01-18

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

PDF

1665

摘要： 通过度再分配的方法研究嵌入到曲面上图的线性荫度.
给定较大亏格曲面\,$\Sigma$\,上嵌入图\,$G$, 如果最大度\,
$\Delta(G)\geq (\sqrt{45-45\varepsilon}+10)$\,且不含\,4-圈,
则其线性荫度为\,$\lceil \frac{\Delta}{2}\rceil$, 其中若\,$\Sigma$\,
是亏格为\,$h(h>1)$\,的可定向曲面时 $\varepsilon=2-2h$, 若\,
$\Sigma$\,是亏格为\,$k(k>2)$\,的不可定向曲面时 $\varepsilon=2-k$.
改进了吴建良的结果, 作为应用证明了边数较少图的线形荫度.

关键词: 线性荫度, 曲面, 嵌入图, 欧拉示性数

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

中图分类号: