An (F3, F5)-partition of planar graphs with girth at least 5

Given a graph G = (V, E), if its vertex set V(G) can be partitioned into two non empty subsets V-1 and V-2 such that Delta(G[V-1]) <= d(1) and Delta(G[V-2]) <= d(2), then we say that G admits a (Delta(d1), Delta(d2)) partition. If G[V-1] and G[V-2] are both forests with maximum degree at most d(1) and d(2), respectively, then we further say that G admits an (F-d1, Fd(2))-partition. Let G(g) denote the class of planar graphs with girth at least g. It is known that every graph in G(5) admits a (Delta(3), Delta(5))-partition Choi and Raspaud (2015) [11]. In this paper, we strengthen this result by proving that every graph in G(5) admits an (F-3, F-5)-partition. (C) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper proves that every graph in G(5) can be partitioned into (F-3, F-5).