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

LV Chang-qing; FANG Yong-lei

Issue 1

Jan. 2013

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2013 > (1): 7-10, 23

LV Chang-qing, FANG Yong-lei. Linear arboricity of an embedded graph on a surface of large genus[J]. Journal of East China Normal University (Natural Sciences), 2013, (1): 7-10, 23.

Citation:

LV Chang-qing, FANG Yong-lei. Linear arboricity of an embedded graph on a surface of large genus[J]. Journal of East China Normal University (Natural Sciences), 2013, (1): 7-10, 23.

LV Chang-qing, FANG Yong-lei. Linear arboricity of an embedded graph on a surface of large genus[J]. Journal of East China Normal University (Natural Sciences), 2013, (1): 7-10, 23.

Citation:

LV Chang-qing, FANG Yong-lei. Linear arboricity of an embedded graph on a surface of large genus[J]. Journal of East China Normal University (Natural Sciences), 2013, (1): 7-10, 23.

PDF( 294 KB)

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

1.
School of Mathematics and Statistics, Zaozhuang University, Zaozhuang Shandong 277160, China

Received Date: 2012-04-01
Rev Recd Date: 2012-07-01
Publish Date: 2013-01-25

Abstract

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(h1)$\,or $\varepsilon=2-k$ if the nonorientable surface with genus \,$k(k2)$. It improves the bound obtained by J. L. Wu. As an application, the linear arboricity of a graph with fewer edges were concluded.
- linear arboricity,
- surface,
- embedded graph,
- Euler characteristic

FullText(HTML)

References(1)

References

[1]

{1}

WU J L. The linear arboricity of graphs on surfaces of negative

Euler characteristic[J]. SIAM J Discrete Math 2008, 23: 54-58.

{2}

BONDY J A, MURTY U S R. Graph Theory with Applications[M].

New York: Macmilan Ltd Press, 1976.
{3}

MOHAR B, THOMASSEN C. Graphs on Surfaces[M]. Baltimore: Johns

Hopkins University Press, 2001: 85-85

{4}

AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs III:

Cyclic and acyclic invariants[J]. Math Slovaca, 1980, 30: 405-417.

{5}

A\"{I}-DJAFER H. Linear arboricity for graphs with multiple

edges[J]. J Graph Theory 1987, 11: 135-140.

{6}

WU J L, WU Y W. The linear arboricity of planar graphs of maximum

degree seven are four[J] J Graph Theory,
{7}

WU J L. On the linear arboricity of planar graphs[J]. J Graph

Theory, 1999, 31: 129-134.
{8}

WU J L. Some path decompositions of Halin graphs[J]. J Shandong

Mining Institute, 1998, 17: 92-96. (in Chinese).
{9}

WU J L. The linear arboricity of series-parallel graphs[J]. Graph

and Combinatorics, 2000, 16: 367-372.
{10}

WU J L, LIU G Z, WU Y L. The linear arboricity of composition

graphs[J]. Journal of System Science and Complexity, 2002, 15(4):

372-375.
{11}

AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs IV:

Linear arboricity[J]. Networks, 1981, 11: 69-72.

Relative Articles

Supplements(0)

Cited By

Proportional views