围长为6平面图的限制森林分解

Partitioning Planar Graphs with Girth at Least 6 into Restricted Forest

摘要: 图$G$ 的$\left({F^{\prime }}_i,{F^{\prime }}_j\right)$ -分解是指把$V\left(G\right)$ 分成两个非空的集合$V_1$ 和$V_2$ ，使得$G\left[V_1\right]$ 和$G\left[V_2\right]$ 分别是每个连通分支边数至多为$i$ 和$j$ 的森林。令${\mathcal{G}}_6$ 表示所有围长$g\ge 6$ 的平面图。本文，我们证明了若$G\in {\mathcal{G}}_6$ 且$G$ 中6-圈与$7^{-}$ -圈不相邻，则$G$ 有$\left({F^{\prime }}_6,{F^{\prime }}_6\right)$ -分解。

Abstract: An $\left({F^{\prime }}_i,{F^{\prime }}_j\right)$ -partition of a graph $G$ is the partition of $V\left(G\right)$ into two non-empty subsets $V_1$ and $V_2$ , so that $G\left[V_1\right]$ and $G\left[V_2\right]$ are both forests whose components have edges at most $i$ and $j$ , respectively. Let ${\mathcal{G}}_6$ denote the family of planar graphs with girth at least 6. In this paper, we prove that if $G\in {\mathcal{G}}_6$ and no adjacent 6- and $7^{-}$ -cycles in $G$ , then $G$ admits an $\left({F^{\prime }}_6,{F^{\prime }}_6\right)$ -partition.