|
|
| |
| The Arboricity of Graphs with Minimum Genus Embeddings |
| |
Citation： |
Dengju MA,Yichao CHEN.The Arboricity of Graphs with Minimum Genus Embeddings[J].Chinese Annals of Mathematics B,2026,(3):511~528 |
| Page view： 93
Net amount： 41 |
Authors： |
Dengju MA; Yichao CHEN |
Foundation： |
the National Natural Science Foundation of China (No. 12271392） |
|
|
| 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 1003 460 + q3g + 16 1 (or 487 244 + q 3 2 h + 16 1 ) 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 √3g + 3 (or q 3 2h + 3) forests in which one has
maximum degree at most 13 √3g + 1 (or 13 q 3 2h + 1). |
Keywords： |
Arboricity Fractional arboricity Surface Minimal genus embedding |
Classification： |
05C10 |
|
|
Download PDF Full-Text
|
