An (F1,F4)‐partition of graphs with low genus and girth at least 6
Min Chen, André Raspaud, Weiqiang Yu · Journal of Graph Theory · 2021
Abstract Let be a graph. If the vertex set can be partitioned into two nonempty subsets and such that and are graphs with maximum degree at most and , respectively, then we say that has a ‐partition. A similar definition can be given for the notation ‐partition if is a forest with maximum degree at most , where . The maximum average degree of is defined to be mad. In this paper, we prove that every graph with mad admits an ‐partition. As a corollary, every graph with low genus and girth at least 6 admits an ‐partition. This improves a result of Borodin and Kostochka saying that every graph with mad admits a ‐partition.