An \((F_3,F_5)\)-partition of planar graphs with girth at least 5
For classes of graphs \(\mathcal{C}_1, \mathcal{C}_2,\dots, \mathcal{C}_k\), a \((\mathcal{C}_1, \mathcal{C}_2,\dots, \mathcal{C}_k)\)-partition of a graph \(G\) is a partition \((V_1, V_2,\dots, V_k)\) of \(V(G)\) with \(G[V_i]\in\mathcal{C}_i\) for each \(i\), \(1\le i\le k\). It is a generalization of a traditional vertex-coloring of a graph. Actually, for a non-negative integer \(d\), let \(\Delta_d\) denote the class of graphs of maximum degree at most \(d\). Then a \(k\)-coloring is a \((\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k)\)-partition with \(\mathcal{C}_1 = \mathcal{C}_2 =\dots =\mathcal{C}_k=\Delta_0\). In particular, The Four Color Theorem states that every planar graph admits a \((\Delta_0, \Delta_0, \Delta_0, \Delta_0)\)-partition. \textit{I. Choi} and \textit{A. Raspaud} [ibid. 338, No. 4, 661--667 (2015; Zbl 1305.05072)] proved that every planar graph of girth at least~\(5\) admits a \((\Delta_3, \Delta_5)\)-partition. In this paper, the authors strengthen this result and prove that every planar graph of girth at least~\(5\) admits an \((F_3, F_5)\)-partition, where \(F_d\) is the class of forests of maximum degree at most \(d\).
scientific article; zbMATH DE number 7622659
scientific article