摘要
通过度再分配的方法研究嵌入到曲面上图的线性荫度.给定较大亏格曲面∑上嵌入图G,如果最大度Δ(G)≥((45-45ε)^(1/2)+10)且不含4-圈,则其线性荫度为[Δ/2],其中若∑是亏格为h(h>1)的可定向曲面时ε=2-2h,若∑是亏格为k(k>2)的不可定向曲面时ε=2-k.改进了吴建良的结果,作为应用证明了边数较少图的线形荫度.
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)≥((45-45ε)^(1/2)+10), then its linear arboricity is [Δ/2], where ε=2-2h if the orientable surface with genus h(h 〉 1) or ε=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.
出处
《华东师范大学学报(自然科学版)》
CAS
CSCD
北大核心
2013年第1期7-10,23,共5页
Journal of East China Normal University(Natural Science)
基金
国家自然科学基金(11101357
61075033)
山东省教育厅高校科研发展计划项目(J09LA57)
关键词
线性荫度
曲面
嵌入图
欧拉示性数
linear arboricity
surface
embedded graph
Euler characteristic