An (F3, F5)-partition of planar graphs with girth at least 5
An (F3, F5)-partition of planar graphs with girth at least 5
复制标题
DOI：
10.1016/j.disc.2022.113216
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Min Chen;A. Raspaud;Weifan Wang;Weiqiang Yu
中科院分区：
文献类型：
--
作者：
Min Chen;A. Raspaud;Weifan Wang;Weiqiang Yu
给定图G=(V， E)，如果它的顶点集V (G)可以划分为两个非空子集v1和v2，使得Δ (G [v1])≤d1和Δ (G [v2])≤d2，那么我们说G允许（Δ d1， Δ d2）划分。如果G [v1]和G [v2]都是最大度最多为d1和d2的森林，则我们进一步说G允许（fd1, fd2）分区。设G G表示周长至少为G的平面图的类别。已知G 5中的每个图都存在（Δ 3， Δ 5）-划分Choi and Raspaud(2015)[11]。在本文中，我们通过证明g5中的每一个图都有一个（f3, f5）分割来加强这一结果。
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 Δ (G [V 1])≤ d 1 and Δ (G [V 2])≤ d 2, then we say that G admits a (Δ d 1, Δ d 2)-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 d 1, F d 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 (Δ 3, Δ 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.