The Arboricity of Graphs with Minimum Genus Embeddings

Abstract

The arboricity of a graph is the minimum number of forests needed to cover all edges of the graph. Let G be a connected graph embedded in a surface. This paper shows that the arboricity of G is at most $\left\lceil {{{1003} \over {460}} + \sqrt {3g + {1 \over {16}}} } \right\rceil$ (or $\left\lceil {{{487} \over {244}} + \sqrt {{3 \over 2}h + {1 \over {16}}} } \right\rceil$) if the orientable genus (or the nonorientable genus) of G is g (or h), and that these bounds are tight. As a conclusion of the results, an upper bound for the outerthickness of a connected graph embedded in an orientable surface (or a non-orientable surface) is obtained. The paper proves that if the orientable genus (or the non-orientable genus) of G is g(≥ 1) (or h), then G can be decomposed into $\lceil {\sqrt {3g} } \rceil + 3$ (or $\left\lceil {\sqrt {{3 \over 2}h} } \right\rceil + 3$) forests in which one has maximum degree at most $\left\lfloor {{1 \over 3}\lceil {\sqrt {3g} }\rceil } \right\rfloor + 1$ (or $\left\lfloor {{1 \over 3}\left\lceil {\sqrt {{3 \over 2}h} } \right\rceil } \right\rfloor + 1$).

Keywords

Arboricity / Fractional arboricity / Surface / Minimal genus embedding / 05C10

References

[1] Balogh J, Kochol M, Pluhár A, Yu X. Covering planar graphs with forests. J. Combin. Theory Ser. B, 2005, 94: 147-158.

[2] Beineke L W. Decomposition of complete graphs into forests. Publ. Math. Inst. Hungar. Acad. Sci., 1964, 9: 589-594

[3] Bondy J A, Murty U S R. Graph Theory, 2008. New York, Springer-Verlag.

[4] Chartrand G, Geller D, Hedetniemi S. Graphs with forbidded subgraphs. J. Combin. Theory Ser. B, 1971, 10: 12-41.

[5] Dean A M, Hutchinson J P, Scheinerman E R. On the thickness and arboricity. J. Combin. Theory Ser. B, 1991, 52: 147-151.

[6] Dujmović V, Wood D R. Graphs treewidth and geometric parameters. Discrete Comput. Geom., 2007, 37: 641-670.

[7] Gonçalaves D. Covering planar graphs with forests, one having bounded maximum degree. J. Combin. Theory Ser. B, 2009, 99: 314-322.

[8] Jiang H B, Yang D Q. Decomposing a graph into forests: The Nine Dragon Tree conjecture is tree. Combinatorica, 2017, 37(6): 1125-1137.

[9] Montassier M, Ossona de Mendez P, Raspaud A, Zhu X D. Decomposing a graph into forests. J. Combin. Theory Ser. B, 2012, 102: 38-52.

[10] Mutzel P, Odenthal T, Scharbrodt M. The thickness of graphs: A survey. Graphs and Combinatorics, 1998, 14: 59-73.

[11] Nash-Williams C St J A. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc., 1961, 36: 445-450.

[12] Nash-Williams C St J A. Decomposition of finite graphs into forests. J. London Math. Soc., 1964, 39: 12.

[13] Parsons T D, Pica G, Pisanski T, Ventre A G S. Orientably simple graphs. Math. Slovaca, 1987, 37: 391-394

[14] Payan C. Graphes equilibre et arboricité rationnelle. European J. Combin., 1986, 7: 263-270.

[15] Ringel G. Map Color Theorem, 1974. Berlin, Springer-Verlag.

[16] White A T. Graphs of Groups on Surfaces, Interactions and Models, 2001. Amsterdam, North-Holland Publishing Co.. 188

[17] Xu B G, Zha X Y. Thickness and outerthickness for embedded graphs. Discrete Math., 2018, 341: 1688-1695.

[18] Yang D Q. Decomposing a graph into forests and a matching. J. Combin. Theory Ser. B, 2018, 131: 40-54.

[19] Youngs J W T. Minimal imbeddings and the genus of a graph. J. Math. Mech., 1963, 12: 303-315

[20] Zha X Y. Edge partition of graphs embeddable in the projective plane and the Klein bottle. J. Math. Res. Appl., 2019, 39(6): 581-592

RIGHTS & PERMISSIONS

The Editorial Office of CAM and Springer-Verlag Berlin Heidelberg