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

\lceil \frac{1003}{460}+\sqrt{3g+\frac{1}{16}}\rceil

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\left\lceil {{{1003} \over {460}} + \sqrt {3g + {1 \over {16}}} } \right\rceil$$\end{document}

(or

\lceil \frac{487}{244}+\sqrt{\frac{3}{2}h+\frac{1}{16}}\rceil

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\left\lceil {{{487} \over {244}} + \sqrt {{3 \over 2}h + {1 \over {16}}} } \right\rceil$$\end{document}

) 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

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\lceil {\sqrt {3g} } \rceil + 3$$\end{document}

(or

\lceil \sqrt{\frac{3}{2}h}\rceil +3

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\left\lceil {\sqrt {{3 \over 2}h} } \right\rceil + 3$$\end{document}

) forests in which one has maximum degree at most

\lfloor \frac{1}{3}\lceil \sqrt{3g}\rceil \rfloor +1

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\left\lfloor {{1 \over 3}\lceil {\sqrt {3g} }\rceil } \right\rfloor + 1$$\end{document}

(or

\lfloor \frac{1}{3}\lceil \sqrt{\frac{3}{2}h}\rceil \rfloor +1

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\left\lfloor {{1 \over 3}\left\lceil {\sqrt {{3 \over 2}h} } \right\rceil } \right\rfloor + 1$$\end{document}

).

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

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.