Covering projective planar graphs with three forests

DOI10.1016/J.DISC.2021.112748MaRDI QIDQ2075505zbMATH OpenOpenAlexFDO

Authors Raiji Mukae, Kenta Ozeki, Terukazu Sano, Ryuji Tazume

Publication date 14 February 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2021.112748

zbMATH Keywords

coveredge partitionforestprojective plane

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A graph \(G\) is said to be \(F(d_1, d_2,\dots,d_k)\)-coverable if \(G\) can be covered by \(k\) forests \(F_1,F_2,\dots,F_k\) such that the maximum degree \(\Delta(F_i)\) is at most \(d_i\) for each \(i=1,2,\dots,k\). If \(d_i=\infty\), then the maximum degree of \(F_i\) is unbounded. \textit{D. Gonçalves} [J. Comb. Theory, Ser. B 99, No. 2, 314--322 (2009; Zbl 1205.05179)] verified that every planar graph is \(F(\infty,\infty,4)\)-coverable. In this paper, the authors prove a similar result for a projective planar graph, that is, they claim that every projective planar graph is \(F(\infty,\infty,4)\)-coverable. Furthermore, they use a new technique to verify the main result.

Recommendations

• Covering planar graphs with forests, one having bounded maximum degree
• Covering planar graphs with forests, one having a bounded maximum degree
• Covering planar graphs with forests
• scientific article; zbMATH DE number 861354
• scientific article; zbMATH DE number 4108779

Cites work

• Computing the orientable genus of projective graphs
• Covering planar graphs with forests
• Covering planar graphs with forests, one having bounded maximum degree
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge‐maximal graphs on orientable and some nonorientable surfaces
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• On the Problem of Decomposing a Graph into n Connected Factors

Cited in

(8)

• Covering planar graphs with forests, one having bounded maximum degree
• Covering planar graphs with forests
• 3-trees in polyhedral maps
• Edge partition of graphs embeddable in the projective plane and the Klein bottle
• Edge covering pseudo-outerplanar graphs with forests
• scientific article; zbMATH DE number 861354 (Why is no real title available?)
• Planar graphs have exponentially many 3-arboricities
• Covering planar graphs with forests, one having a bounded maximum degree

This page was built for publication: Covering projective planar graphs with three forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2075505)