ABSTRACT

An (F, F_d)-partition of a graph G is a vertex partition of its vertex set into subsets F and F_d such that G[F] is a forest, while G[F_d] is a forest of maximum degree at most d. In this paper, we prove that every planar graph without 4-cycles and 5-cycles admits an (F, F₅)-partition.

Keywords:Vertex Partition, Forest, Maximum Degree

平面图的(F, F_d)-分解问题

俞伟强

浙江师范大学数学与计算机科学学院，浙江 金华

收稿日期：2019年7月4日；录用日期：2019年7月19日；发布日期：2019年7月26日

摘 要

图G的(F, F_d)-分解是指将G的顶点集合划分为两个子集F和F_d，使得G[F]为森林，G[F_d]为最大度至多为d的森林。本文证明了每一个不含4-圈和5-圈的平面图都存在(F, F₅)-分解。

关键词 :顶点分解，森林，最大度

Copyright © 2019 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文提及的图都是有限简单无向图。假设 $G=\left(V,E\right)$ 。令 $G_1,\cdots ,G_m$ 表示m个图类。如果 $V\left(G\right)$ 可以被分解为m个集合 $V_1,\cdots ,V_m$ ，使得对于 $1\le l\le m$ ，子图 $G\left[V_l\right]$ 属于图类 $G_l$ ，那么我们称其为图G的一个 $\left(G_1,\cdots ,G_m\right)$ -分解。为简单起见，我们用F，I， ${\Delta }_k$ 和 $F_k$ 分别表示图类森林，独立集，最大度为k的图和最大度为k的森林。文中的三角形指3-圈。如果两个圈或面至少有一条公共边，则称它们相邻。如果两个圈或面至少有一个公共点，则称它们相交。

著名的四色定理 [1] [2] 告诉我们每一个平面图都存在 $\left(I,I,I,I\right)$ -分解。并且根据无圈染色问题的相关研究，在1976年，Borodin [3] 证明了每一个平面图都存在 $\left(I,F,F\right)$ -分解。此后，在1990年，Poh [4] 证明了每一个平面图都存在 $\left(F_2,F_2,F_2\right)$ -分解。但是，早在1969年，Chartrand [5] 等人就找到了不存在 $\left(F,F\right)$ -分解的平面图。

另一方面，2008年，Raspaud和Wang [6] 证明了每一个不含距离小于2的三角形或对于某个 $k\in \left(3,4,5,6\right)$ ，不含k-圈的平面图都存在 $\left(F,F\right)$ -分解。此外，在不久后Chen，Raspaud和Wang [7] 成功证明了每一个不含相交三角形的平面图都存在 $\left(F,F\right)$ -分解。最近，Dross和Montassier [8] 证明了每一个不含3-圈的平面图存在 $\left(F,F_5\right)$ -分解。

本文证明了如下结果：

定理 每一个不含4-圈和5-圈的平面图都存在 $\left(F,F_5\right)$ -分解。

接下来给出文中的一些基本记号。G中点v的度数用 $d_G\left(v\right)$ 表示。我们分别用k-点， $k^{+}$ -点和 $k^{-}$ -点表示度为k的点，度至少为k的点和度至多为k的点。同理定义k-面， $k^{+}$ -面和 $k^{-}$ -面。称G中的 $8^{+}$ -点为大点，否则为小点。因此v的 $8^{+}$ -邻点称为大邻点，否则称为小邻点。称v在F中的邻点为F-邻点。用 $n_b\left(v\right)$ 表示v的大邻点的个数。对于 $f\in F\left(G\right)$ ，若f的边界点按顺时针方向排列依次为 $v_1,v_2,\cdots ,v_n$ ，则可记作 $f=\left[v_1{v}_2\cdots v_n\right]$ 。并且令 $f_i$ 表示以 $v_i{v}_{i+1}$ 为公共边与f相邻的面，其中 $i=1,2,\cdots ,n$ 且i对n取模。对于m-面 $f=\left[v_1{v}_2\cdots v_m\right]$ ，若 $v_i$ 的度数为 $a_i$ ，则可记f为 $\left(a_1,a_2,\cdots ,a_m\right)$ -面。假设v为k-点，令 $v_1,v_2,\cdots ,v_k$ 为按顺时针方向排列的邻点，则 $g_i$ 表示以 $v{v}_i$ 和 $v{v}_{i+1}$ 为边界与v关联的面，其中 $i=1,2,\cdots ,k$ 且i对k取模。

对于集合 $S\subset V$ ，令 $G-S$ 表示在G中删去所有的S中的点及其关联的边所得的图。对于与V不交的点集S，令 $G+S$ 表示在G中加上S中的点所得的图。对于与E不交的边集 $E^{\prime }$ ，令 $G+E^{\prime }$ 表示在G中加上 $E^{\prime }$ 中的边所得的图。

2. 定理证明

2.1. 极小反例的结构性质

假设 $G=\left(V,E\right)$ 为上述定理点数最少的极小反例。显然，G是连通的，否则我们可以找到一个点数更小的极小反例。首先我们给出G的一些结构性质。

断言 1 G中不存在 $2^{-}$ -点。

证明 假设v为G中的 $2^{-}$ -点。根据G的极小性可得， $G-v$ 存在 $\left(F,F_5\right)$ -分解。如果 $d\left(v\right)=1$ ，那么我们可将v放入F。假设 $d\left(v\right)=2$ ，若它的两个邻点都在F中，则可将v放入 $F_5$ 。否则v至少有一个邻点在 $F_5$ 中，此时我们可将v放入F。因此我们总能得到G的 $\left(F,F_5\right)$ -分解，矛盾。

断言 2 G中的3-点至少相邻一个大点。

证明 假设 $d\left(v\right)=3$ 且它的邻点都为小点，即 $7^{-}$ -点。根据G的极小性可得， $G-v$ 存在 $\left(F,F_5\right)$ -分解。如果v的三个邻点中至少有两个在 $F_5$ 中，那么我们可将v放入F。如果它的三个邻点都在F中，那么我们可将v放入 $F_5$ 。现在假设v恰好有一个邻点u在 $F_5$ 中。如果u至多有一个F-邻点，那么我们可将u放入F，v放入 $F_5$ 。否则因为u为小点，它至多有四个 $F_5$ -邻点，此时我们可将v放入 $F_5$ 。因此我们总能得到G的 $\left(F,F_5\right)$ -分解，矛盾。

断言 3 G中不存在6-面 $f=\left[v_1{v}_2\cdots v_6\right]$ 使得 $f_1,f_2,f_3$ 是三角形，且 $d\left(v_i\right)=3$ ， $i=1,2,\cdots ,6$ ，或当 $v_1$ 只有一个大邻点时， $d\left(v_1\right)=4$ ， $d\left(v_i\right)=3$ ， $i=2,3,\cdots ,6$ 。

证明 不妨设 $f=\left[v_1,v_2,\cdots ,v_6\right]$ 为G中满足断言1的6-面，令 $u_1,u_2,u_3$ 分别为与 $f_1,f_3,f_5$ 关联的第三个点，且令 $v_1$ 的第四个邻点为 $u_4$ 。则由断言2， $u_i$ 为大点， $i=1,2,3$ 。令 $G^{\prime }=G-\left\{v_1,v_2,v_3,v_4,v_5,v_6\right\}+\left\{w_1,w_2,w_3\right\}$ $+\left\{w_1{w}_2,w_2{w}_3,w_3{w}_1,w_1{u}_1,w_2{u}_2,w_3{u}_3\right\}$ ，则 $G^{\prime }$ 中不存在4-圈和5-圈。由G的极小性可得，G存在 $\left(F,F_5\right)$ -分解。我们要证明在下列所有情况下我们都可以得到G的 $\left(F,F_5\right)$ -分解。在下列情形中，若 $u_4$ 在 $F_5$ 中，则将 $v_1$ 放入 $F_5$ 可能会增加 $G\left[F_5\right]$ 中点的度数，此时因为 $u_4$ 是小点我们可以将它 $u_4$ 放入F。

· 若 $u_1,u_2,u_3$ 都在F中，则我们将 $v_2$ 放入F， $v_1,v_3,v_4,v_5$ 放入 $F_5$ 。

· 若 $u_1,u_2,u_3$ 恰好有一个点在 $F_5$ 中。设 $u_i$ 在 $F_5$ 中，则我们将与 $f_i$ 关联的另外两个点放入F，将与f关联的另外四个点放入 $F_5$ 。

· 若 $u_1,u_2,u_3$ 恰好有两个点在 $F_5$ 中。设 $u_i,u_j$ 在 $F_6$ 中，则我们将与 $f_i,f_j$ 关联的另外两个点放入F，将与f关联的另外两个点放入 $F_5$ 。

· 若 $u_1,u_2,u_3$ 都在 $F_5$ 中。由于 $G^{\prime }\left[\left\{w_1,w_2,w_3\right\}\right]$ 为 $G^{\prime }$ 中的三角形，则至少有一个点在 $F_5$ 中。若 $w_1$ 在 $F_5$ 中，则将 $v_2$ 放入 $F_5$ ，将 $v_1,v_3,v_4,v_5,v_6$ 放入F，若 $w_i$ 在 $F_5$ 中， $i=2,3$ ，则我们将与 $f_i$ 关联的一个点放入 $F_5$ 且将其余与f关联的点放入F。

因此在任意情况下G都存在 $\left(F,F_5\right)$ -分解，矛盾。

断言 4 若 $f=\left[v_1{v}_2\cdots v_6\right]$ 为 $\left(3,3,3,3,3,8^{+}\right)$ -面， $f_3,f_5,f_6$ 为三角形，且与 $f_5,f_6$ 关联的第三个点为小点，则 $d\left(v_6\right)\ge 9$ 。

证明 设 $f=\left[v_1{v}_2\cdots v_6\right]$ 为上述6-面，令 $v_2$ 的第三个邻点和与 $f_3,f_5,f_6$ 关联的第三个点分别为 $u_1,u_2,u_3,u_4$ 。令 $G^{\prime }=G-\left\{v_2\right\}$ ，则由G的极小性， $G^{\prime }$ 存在 $\left(F,F_5\right)$ -分解。当 $d\left(v_6\right)=8$ 时，我们可以很容易地将 $G^{\prime }$ 的 $\left(F,F_5\right)$ -分解扩充到G。

首先假设 $u_1$ 在F中。若 $v_1,v_3$ 中至多一个属于 $F_5$ ，则可将 $v_2$ 放入 $F_5$ 。否则可将 $v_2$ 放入F。现在假设 $u_1$ 在 $F_5$ 中。若 $v_1,v_3$ 中至多一个属于F，则可将 $v_2$ 放入F。因此可以假设两者都在F中。若 $u_4,v_6$ 都在 $F_5$ 中，则同样可将 $v_2$ 放入F。若两者都在F中，则可先将 $v_1$ 放至 $F_5$ ，再将 $v_2$ 放至F。否则，首先假设 $u_4$ 在 $F_5$ 中， $v_6$ 在F中，若 $u_4$ 至多有四个 $F_5$ -邻点，则可同样将 $v_1$ 放至 $F_5$ 。若有至少五个 $F_5$ -邻点，则可将 $u_4$ 放至F， $v_1$ 放至 $F_5$ 。因此可得 $u_4$ 在F中， $v_6$ 在 $F_5$ 中。

同上分析可得 $v_i$ 和 $u_3$ 一定在F中， $i=4,5$ ，且 $u_2$ 一定在 $F_5$ 中。若 $d\left(v_6\right)=8$ ，则 $v_6$ 至多有四个 $F_5$ -邻点。因此我们可以将 $v_1$ 或者 $v_5$ 放入 $F_5$ 。 $v_2$ 放入F。因此我们总能得到G的 $\left(F,F_5\right)$ -分解，矛盾。

断言 5 设 $f=\left[v_1{v}_2\cdots v_6\right]$ 为G中的 $\left(3,8^{+},3,3,8^{+}3\right)$ -面，其中 $f_i$ 为三角形， $i=1,2,4,5$ 。令与 $f_i$ 关联的第三个点为 $u_i$ 。若 $u_i$ 为小点， $i=1,2,4,5$ ，则 $v_2,v_5$ 中至少有一个 $9^{+}$ -点。特别地，若 $u_1,u_5$ 或 $u_2,u_4$ 为3-点，则 $v_2,v_5$ 都为 $9^{+}$ -点。

证明 设 $v_2,v_5$ 都为8-点。令 $G^{\prime }=G-\left\{v_1,v_6\right\}$ ，由G的极小性可得， $G^{\prime }$ 存在 $\left(F,F_5\right)$ -分解。下面我们要证明G存在 $\left(F,F_5\right)$ -分解，从而得出矛盾，从而证明 $v_2,v_5$ 中至少有一个 $9^{+}$ -点。

· 首先假设 $v_2,v_5$ 都在F中。若 $u_1,u_5$ 都在F中，则将 $v_1,v_6$ 放入 $F_5$ 。否则，由于 $u_1,u_5$ 都是小点，可将 $v_1$ 放入 $F_5$ ， $v_6$ 放入F。

· 假设 $v_2,v_5$ 恰好有一个点在F中，由对称性不妨设 $v_2$ 在F中且 $v_5$ 在 $F_5$ 中。此时可将 $v_1$ 放入 $F_5$ ， $v_5$ 放入F。

· 设 $v_2,v_5$ 都在 $F_5$ 中。若 $u_1,u_5$ 中至多有一个点在 $F_5$ 中，则将 $v_1,v_6$ 放入F。现在假设 $u_1,u_5$ 都在F中。由于 $v_3,u_2$ 中至多有一个点在 $F_5$ 中，若 $v_2$ 其余的邻点不都在 $F_5$ 中，则将 $v_1$ 放入 $F_5$ ， $v_6$ 放入F。因此， $v_3,u_2$ 和 $v_4,u_4$ 中都恰好有一个点在 $F_5$ 中。

(1) 如果 $u_2$ 在F中，则将 $v_3$ 放入F， $v_1$ 放入 $F_5$ ， $v_6$ 放入F。

(2) 如果 $u_2$ 在 $F_5$ 中，则将 $v_2$ 放入F， $v_1$ 放入 $F_5$ ， $v_6$ 放入F。

若 $u_2,u_4$ 都为3-点，由对称性不妨设 $d\left(v_2\right)=8$ 。我们知道 $v_2,u_2$ 中恰好有一个点在 $F_5$ 中，且 $v_4,u_4$ 中至少有一个点在F中。令 $u_2,u_4$ 的第三个邻点分别为 $w_1,w_2$ 。

· 设 $u_2$ 在 $F_5$ 中。若 $v_4$ 在F中，则我们将 $v_3$ 放入 $F_5$ ， $v_2$ 放入F， $v_1$ 放入 $F_5$ 且将 $v_6$ 放入F。否则， $v_4$ 在 $F_5$ 中且 $u_4$ 在F中。若 $w_2$ 在 $F_5$ 中，则将 $v_4$ 放入F，则我们回到了之前讨论过的情况。否则，将 $v_4$ 放入F，同样回到之前讨论过的情况。

· 设 $v_3$ 在 $F_5$ 中。若 $w_1$ 在F中，我们将 $v_3$ 放入 $F_5$ ， $v_2$ 放入F， $v_1$ 放入 $F_5$ 且将 $v_6$ 放入F。否则，我们直接将 $v_2$ 放入F， $v_1$ 放入 $F_5$ ， $v_6$ 放入F。

2.2. 权转移

接下来我们将应用权转移来得出矛盾。首先我们对G中的顶点和边定义初始权函数 $\omega$ 。对于 $v\in V\left(G\right)$ ， $\omega \left(v\right)=2d\left(v\right)-6$ ；对于 $f\in F\left(G\right)$ ， $\omega \left(f\right)=d\left(f\right)-6$ 。根据欧拉公式和握手定理可得

${\displaystyle {\sum }_{v\in V\left(G\right)}\left(2d\left(v\right)-6\right)}+{\displaystyle {\sum }_{f\in F\left(G\right)}\left(d\left(f\right)-6\right)}=-12$ 。

然后定义适当的权规则将初始权 $\omega$ 通过权转移变为最终权 ${\omega }^{\text{*}}$ ，使得对于每个 $x\in V\left(G\right)\cup F\left(G\right)$ ，有 ${\omega }^{\text{*}}\left(x\right)\ge 0$ 。注意到权转移过程不会改变总的权和，因此我们可以得出如下矛盾， $0\le {\displaystyle {\sum }_{x\in V\left(G\right)\cup F\left(G\right)}{\omega }^{*}\left(x\right)}={\displaystyle {\sum }_{x\in V\left(G\right)\cup F\left(G\right)}\omega \left(x\right)}=-12$ ，从而完成定理的证明。

设 $d\left(v\right)=4$ 。令 $v_1,v_2,v_3,v_4$ 为v在平面上按顺时针方向排列的邻点。记以 $v{v}_i$ 和 $v{v}_{i+1}$ 为边界构成的面为 $f_i$ ， $i=1,2,3,4$ 且i对4取模。设 $f=\left[v_1{v}_2\cdots v_6\right]$ 是一个6-面，若 $f_i$ 是一个三角形，则令 $u_i$ 为与 $f_i$ 关联的第三个点。

若v是一个3-点，关联一个三角形且只有一个大邻点，则称v为一个坏3-点。另外，若v是一个4-点且关联两个三角形，则称v为坏4-点。设 $f=\left[v_1{v}_2\cdots v_6\right]$ 是一个 $\left(3,8^{+},3,3,8^{+},3\right)$ -面且 $f_i$ 为三角形， $i=1,2,4,5$ 。若 $u_i$ 是小点， $i=1,2,4,5$ ，且 $u_1,u_5$ 或者 $u_2,u_4$ 不都为3-点，则称f是一个坏6-面。很显然，任意两个坏6-面不相邻。

对于 $x,y\in V\left(G\right)\cup F\left(G\right)$ ，我们用 $\tau \left(x\to y\right)$ 表示x转给y的权值。另外，用 $l\left(v\right)$ 表示与v关联的三角形的个数。对于任意 $f\in F\left(G\right)$ ，用 $k\left(f\right)$ 表示与f关联的坏3-面的个数。我们的权规则定义如下：

(R1) 令 $d\left(v\right)=3$ 。若 $l\left(v\right)=0$ ，则v给每个关联的6⁺-面转权 $\frac{n_b\left(v\right)}{4}$ 。设 $l\left(v\right)=1$ ，若v是一个坏3-点，则v给每个关联的三角形转权1。否则，v给每个关联的三角形转权1，给每个关联的6⁺-面转权 $\frac{3n_b\left(v\right)-4}{8}$ 。

(R2) 令 $d\left(v\right)=4$ 。若 $l\left(v\right)=0$ ，则v给每个关联的 $6^{+}$ -面转权 $\frac{3n_b\left(v\right)+8}{16}$ 。当 $l\left(v\right)=1$ 时，令 $f_i$ 为三角形，则 $\tau \left(v\to f_i\right)=1$ ， $\tau \left(v\to f_2\right)=\tau \left(v\to f_4\right)=\frac{3n_b\left(v\right)+2}{8}$ 且 $\tau \left(v\to f_3\right)=\frac{1}{2}$ 。设 $l\left(v\right)=2$ ，则v给每个关联的三角形转权1，给每个关联的 $6^{+}$ -面转权 $\frac{3n_b\left(v\right)}{8}$ 。

(R3) 5-点给每个关联的三角形转权1，给每个关联的 $6^{+}$ -面转权 $\frac{n_b\left(v\right)+2}{3}$ 。

(R4) 小 $6^{+}$ -点给每个关联的面转权1。

(R5) 令v为G中的一个大点，则

(R5.1) v给每个相邻的小点转 $\frac{3}{4}$ 。若v相邻一个大点u，则v给每个与v关联且以uv为边界的面转权 $\frac{3}{8}$ 。

(R5.2) v给每个关联的三角形转权1。 $9^{+}$ -点给每个关联的 $6^{+}$ -面转权 $\frac{1}{4}$ 。每个6-点给关联的 $6^{+}$ -面 $f^{\prime }$ 转权 $\frac{1}{8}$ ，其中 $f^{\prime }$ 至多相邻一个与v关联的三角形。

(R6) $6^{+}$ -面给每个关联的坏3-点转权 $\frac{1}{8}$ ，给每个相邻的坏6-面转权 $\frac{1}{8}$ 。

下面我们证明对于所有 $x\in V\left(G\right)\cup F\left(G\right)$ ， ${\omega }^{*}\left(x\right)\ge 0$ 。令 $v\in V\left(G\right)$ ，则 $d\left(v\right)\ge 3$ 。

· 设 $d\left(v\right)=3$ 。若 $l\left(v\right)=0$ ，则由(R1)和(R5)可得 ${\omega }^{*}\left(v\right)\ge \frac{3}{4}{n}_b\left(v\right)-3\cdot \frac{n_b\left(v\right)}{4}\ge 0$ 。若 $l\left(v\right)=1$ ，假设v是一个坏3-点，则根据规则(R1)，(R5)和(R6)我们可以得出 ${\omega }^{*}\left(v\right)\ge 1-\frac{3}{4}-2\cdot \frac{1}{8}\ge 0$ 。否则， ${\omega }^{*}\left(v\right)\ge -1-2\cdot \frac{3n_b\left(v\right)-4}{8}+\frac{3n_b\left(v\right)}{4}\ge 0$ 。

· 设 $d\left(v\right)=4$ 。若 $l\left(v\right)=0$ ，则由(R2)和(R5)可得 ${\omega }^{*}\left(v\right)\ge \frac{3n_b\left(v\right)}{4}+2-4\cdot \frac{3n_b\left(v\right)+8}{16}\ge 0$ 。若 $l\left(v\right)=1$ ，则 ${\omega }^{*}\left(v\right)\ge \frac{3n_b\left(v\right)}{4}+2-1-2\cdot \frac{3n_b\left(v\right)+2}{8}-\frac{1}{2}\ge 0$ 。设 $l\left(v\right)=2$ ，则 ${\omega }^{*}\left(v\right)\ge \frac{3n_b\left(v\right)}{4}+2-2-2\cdot \frac{3n_b\left(v\right)}{8}\ge 0$ 。

· 设 $d\left(v\right)=5$ ，由(R3)我们可以得到 ${\omega }^{*}\left(v\right)\ge 4+n_b\left(v\right)-2-3\cdot \frac{n_b\left(v\right)+2}{3}\ge 0$ 。

· 设 $6\le d\left(v\right)\le 7$ ，由(R4)我们可以得到 ${\omega }^{*}\left(v\right)\ge 2d\left(v\right)-6-d\left(v\right)\ge 0$ 。

· 设 $d\left(v\right)=8$ ，由(R5)我们可以得到 ${\omega }^{*}\left(v\right)\ge 2\cdot 8-6-8\cdot \frac{3}{4}-4\ge 0$ 。

· 设 $d\left(v\right)\ge 9$ 。如果 $d\left(v\right)=9$ ，则根据(R5)可得 ${\omega }^{\text{*}}\left(v\right)\ge 12-9\cdot \frac{3}{4}-5\cdot \frac{1}{4}-4=0$ 。如果 $d\left(v\right)\ge 10$ ，则根据(R5)可得 ${\omega }^{\text{*}}\left(v\right)\ge 2d\left(v\right)-6-\frac{d\left(v\right)}{2}-\frac{3d\left(v\right)}{4}-\frac{1}{4}\cdot \left(\frac{d\left(v\right)}{2}+1\right)\ge 0$ 。

下面我们证明对于 $f\in F\left(G\right)$ ，有 ${\omega }^{\text{*}}\left(f\right)\ge 0$ 。如果 $d\left(f\right)=3$ ，那么根据规则(R1)-(R5)我们可以得出 ${\omega }^{*}\left(f\right)\ge -3+3=0$ 。如果 $d\left(f\right)=7$ ，则f的边界上至多有6个坏3-点并且f至多相邻两个坏6-面。因此

${\omega }^{*}\left(f\right)\ge 1-6\cdot \frac{1}{8}-2\cdot \frac{1}{8}=0$ 。设 $d\left(f\right)\ge 8$ ，有 ${\omega }^{*}\left(f\right)\ge d\left(f\right)-6-\frac{1}{8}\cdot d\left(f\right)-\frac{1}{8}\cdot \frac{1}{2}\cdot d\left(f\right)>0$ 。现在假设 $d\left(f\right)=6$ ，令 $f=\left[v_1{v}_2\cdots v_6\right]$ 。接下来我们将根据 $k\left(f\right)$ 的值将证明分为以下几个部分。注意到不是坏3-点的3-点和小 $4^{+}$ -点至少给每个关联的 $6^{+}$ -面转权 $\frac{1}{4}$ 。

情况 1 假设 $k\left(f\right)=0$ ，则有 ${\omega }^{*}\left(f\right)=\omega \left(f\right)=d\left(f\right)-6=0$ 。

情况 2 假设 $k\left(f\right)=1$ ，则f不相邻坏6-面。令 $v_1$ 为坏3-点， $f_1$ 为三角形。则 $f_6$ 一定为 $4^{+}$ -面。因此不管 $v_6$ 是大点还是小点，都有 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。从而有 ${\omega }^{*}\left(f\right)\ge -\frac{1}{8}+\frac{1}{4}>0$ 。

情况 3 假设 $k\left(f\right)=2$ 。

首先假设 $v_1,v_2$ 为坏3-点。如果 $f_1$ 为三角形，那么 $f_2,f_6$ 都为 $4^{+}$ -面，因此 $\tau \left(v_3\to f\right)\ge \frac{1}{4}$ ， $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。故有 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-2\cdot \frac{1}{8}>0$ 。现在假设 $f_2,f_6$ 为三角形，如果 $v_3$ 为小点，那么 $u_2$ 肯定为大点，因此根据规则(R1)-(R4)可得 $\tau \left(v_3\to f\right)\ge \frac{3}{8}$ 。从而有 ${\omega }^{*}\left(f\right)\ge \frac{3}{8}-2\cdot \frac{1}{8}-\frac{1}{8}=0$ 。假设 $v_3$ 为大点，如果 $v_4$ 也为大点，则根据规则(R5.1)可得 $\tau \left(v_3\to f\right)\ge \frac{3}{8}$ ；否则 $\tau \left(v_4\to f\right)\ge \frac{1}{4}$ 。由对称性可得 $\tau \left(v_5\to f\right)+\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-2\cdot \frac{1}{8}>0$ 。

假设 $v_1,v_3$ 为坏3-点。如果 $f_1,f_2$ 为三角形，那么 $f_3,f_6$ 都为 $4^{+}$ -面，因此有 $\tau \left(v_4\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ ，故 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-2\cdot \frac{1}{8}>0$ 。现在假设 $f_3,f_6$ 为三角形，由于 $f_1,f_2$ 为 $4^{+}$ -面且 $v_2$ 不为坏点，因此 $\tau \left(v_2\to f\right)\ge \frac{1}{4}$ ，故 ${\omega }^{*}\left(f\right)\ge \frac{1}{4}-2\cdot \frac{1}{8}=0$ 。根据对称性我们假设 $f_1,f_3$ 为三角形，那么 $v_2$ 必为 $4^{+}$ -点且不为坏点，因此 ${\omega }^{*}\left(f\right)\ge \frac{1}{4}-2\cdot \frac{1}{8}=0$ 。

假设 $v_1,v_4$ 为坏3-点。由对称性，如果 $f_1,f_3$ 为三角形，那么 $f_4,f_6$ 必为 $4^{+}$ -面。由于 $v_5,v_6$ 都不为坏点，因此 $\tau \left(v_5\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。故 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-2\cdot \frac{1}{8}>0$ 。如果 $f_1,f_4$ 为三角形，那么 $f_3,f_6$ 为 $4^{+}$ -面，同样我们有 $\tau \left(v_3\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-2\cdot \frac{1}{8}>0$ 。

情况 4 假设 $k\left(f\right)=3$ 。

假设 $v_1,v_2,v_3$ 为坏3-点。根据对称性假设 $f_1,f_3$ 为三角形，则有 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。如果 $v_4$ 为小点，那么 $u_3$ 肯定为大点，因此根据(R2)-(R4)可得 $\tau \left(v_4\to f\right)\ge \frac{1}{4}$ 。假设 $v_4$ 为大点，如果 $v_5$ 也是大点，那么根据规则(R5)有 $\tau \left(v_4\to f\right)\ge \frac{3}{8}$ 。否则 $\tau \left(v_5\to f\right)\ge \frac{1}{4}$ 。因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-3\cdot \frac{1}{8}-\frac{1}{8}=0$ 。

假设 $v_1,v_2,v_4$ 为坏3-点。如果 $f_1,f_3$ 为三角形，那么根据以上讨论我们可得 $\tau \left(v_5\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-3\cdot \frac{1}{8}>0$ 。假设 $f_1,f_4$ 为三角形，同样可得 $\tau \left(v_3\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-3\cdot \frac{1}{8}>0$ 。假设 $f_2,f_3,f_6$ 为三角形。如果 $v_3$ 为小点，那么 $u_2$ 肯定为大点，因此根据规则(R2)， $\tau \left(v_3\to f\right)\ge \frac{3}{8}$ 。由于 $f_4$ 为 $4^{+}$ -面， $v_5$ 不为坏点，因此 $\tau \left(v_5\to f\right)\ge \frac{1}{4}$ ，故 ${\omega }^{*}\left(f\right)\ge \frac{1}{4}+\frac{3}{8}-3\cdot \frac{1}{8}>0$ 。现在假设 $v_3$ 为大点，那么 $v_5$ 肯定为小点。同样有 $\tau \left(v_5\to f\right)\ge \frac{1}{4}$ 。如果 $v_6$ 为小点，那么 $u_6$ 肯定为大点，因此根据规则(R2)， $\tau \left(v_6\to f\right)\ge \frac{3}{8}$ 。否则假设 $v_6$ 为大点，如果 $f_5$ 为三角形，那么根据规则(R2)有 $\tau \left(v_5\to f\right)\ge \frac{5}{8}$ ，或根据规则(R5)有 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。在每种情况下我们都有 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-3\cdot \frac{1}{8}-\frac{1}{8}=0$ 。最后假设 $f_2,f_4,f_6$ 为三角形。此时 $v_3$ 为 $4^{+}$ -点且 $f_3$ 为 $4^{+}$ -面。如果 $v_3$ 为小点，那么 $u_2$ 肯定为大点，因此根据规则(R2)， $\tau \left(v_3\to f\right)\ge \frac{5}{8}$ 。现在假设 $v_3$ 为大点，由于f为 $4^{+}$ -面， $\tau \left(v_3\to f\right)\ge \frac{1}{4}$ 。并且 $v_5$ 为小点，那么 $u_6$ 肯定为大点，因此根据规则(R2)， $\tau \left(v_6\to f\right)\ge \frac{5}{8}$ 。否则 $\tau \left(v_5\to f\right)\ge \frac{3}{8}$ 。因此总有 ${\omega }^{*}\left(f\right)\ge \frac{5}{8}-\frac{3}{8}-\frac{1}{8}>0$ 。

假设 $v_1,v_3,v_5$ 为坏3-点。首先假设 $f_1,f_2,f_4$ 为三角形，则 $f_3,f_5,f_6$ 必为 $4^{+}$ -面，因此 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_4\to f\right)\ge \frac{1}{4}$ 。故 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-\frac{3}{8}>0$ 。现在假设 $f_1,f_3,f_5$ 为三角形，同样可得 $\tau \left(v_2\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_4\to f\right)\ge \frac{1}{4}$ 。因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-\frac{3}{8}>0$ 。

情况 5 假设 $k\left(f\right)=4$ 。

假设 $v_1,v_2,v_3,v_4$ 为坏3-点。首先假设 $f_1,f_3$ 为三角形，那么f不相邻坏6-面。并且 $f_4,f_6$ 都为 $4^{+}$ -面，因此 $\tau \left(v_5\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。故 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-4\cdot \frac{1}{8}>0$ 。现在假设 $f_2,f_4,f_6$ 为三角形，如果 $v_5,v_6$ 都为大点，那么 $\tau \left(v_5\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。如果 $v_5,v_6$ 都为小点，那么 $u_4,u_6$ 都为大点，因此根据规则(R2)同样有 $\tau \left(v_5\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。否则根据对称性假设 $v_5$ 为大点而 $v_6$ 为小点，此时 $u_6$ 肯定为大点，因此 $\tau \left(v_6\to f\right)\ge \frac{3}{4}$ 。故 ${\omega }^{*}\left(f\right)\ge \frac{3}{4}-4\cdot \frac{1}{8}-2\cdot \frac{1}{8}=0$ 。

假设 $v_1,v_2,v_3,v_5$ 为坏3-点。首先假设 $f_1,f_3,f_4$ 为三角形，那么 $f_5,f_6$ 肯定为 $4^{+}$ -面，因此根据规则(R1)， $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。此时如果 $v_4$ 为小点，那么 $u_3,u_4$ 肯定为大点，因此根据(R3) $\tau \left(v_4\to f\right)\ge \frac{2}{3}$ ，故 ${\omega }^{*}\left(f\right)\ge \frac{1}{4}+\frac{2}{3}-\frac{1}{2}-\frac{1}{8}>0$ 。现在假设 $v_4$ 为大点，根据断言4， $d\left(v_4\right)\ge 9$ ，此外 $f_2$ 不为坏面，因此 $\tau \left(v_4\to f\right)\ge \frac{1}{4}$ 。从而有 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-\frac{1}{2}=0$ 。假设 $f_2,f_4,f_6$ 为三角形，那么 $f_3,f_5$ 肯定为 $4^{+}$ -面且 $v_4$ 为小 $4^{+}$ -点，因此 $\tau \left(v_4\to f\right)\ge \frac{1}{4}$ 。此时如果 $v_6$ 为大点，那么 $f_1$ 肯定不为坏面且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ ，因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-\frac{1}{2}=0$ 。否则 $u_6$ 肯定为大点，因此根据规则(R2)， $\tau \left(v_6\to f\right)\ge \frac{5}{8}$ 。从而有 ${\omega }^{*}\left(f\right)\ge \frac{5}{8}+\frac{1}{4}-\frac{1}{2}-\frac{1}{8}>0$ 。

假设 $v_1,v_2,v_4,v_5$ 为坏3-点。首先假设 $f_1,f_4$ 为三角形，那么f相邻的其余面都为 $4^{+}$ -面，此时有 $\tau \left(v_3\to f\right)\ge \frac{1}{4}$ 且 $\tau \left(v_6\to f\right)\ge \frac{1}{4}$ 。因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-\frac{1}{2}=0$ 。假设 $f_1,f_3,f_5$ 为三角形，那么此时 $f_2,f_6$ 为 $4^{+}$ -面。如果 $v_3,v_6$ 都为大点，那么 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-\frac{1}{2}=0$ 。否则 $v_3,v_6$ 都为小点并且 $u_3,u_5$ 都为大点，因此根据规则(R2)， $\tau \left(v_3\to f\right)\ge \frac{5}{8}$ ，故 ${\omega }^{*}\left(f\right)\ge \frac{5}{8}-\frac{1}{2}>0$ 。最后假设 $f_2,f_3,f_5,f_6$ 为三角形，如果 $v_3,v_6$ 都为小点，那么对于 $i=2,3,5,6$ ， $u_i$ 都为大点。根据规则(R3)， $\tau \left(v_3\to f\right)\ge \frac{2}{3}$ ， $\tau \left(v_6\to f\right)\ge \frac{2}{3}$ ，因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{2}{3}-\frac{1}{2}-2\cdot \frac{1}{8}>0$ 。现在假设 $v_3,v_6$ 中恰有一个为小点，不妨设为 $v_3$ ，此时 $f_1,f_4$ 不为坏面，因此我们同样可得 $\tau \left(v_3\to f\right)\ge \frac{2}{3}$ ， ${\omega }^{*}\left(f\right)\ge \frac{2}{3}-\frac{1}{2}>0$ 。最后假设 $v_3,v_6$ 都为大点，那么对于 $i=2,3,5,6$ ， $u_i$ 都为小点。根据断言5，如果 $u_2,u_6$ 或 $u_3,u_5$ 都为3-点，那么 $v_3,v_6$ 都为 $9^{+}$ -点。因此 ${\omega }^{*}\left(f\right)\ge 2\cdot \frac{1}{4}-\frac{1}{2}=0$ 。否则f为坏6-面，同样根据断言5， $v_3,v_6$ 中至少有一个点为 $9^{+}$ -点，因此根据规则(R6)， $\tau \left(f_1\to f\right)\ge \frac{1}{8}$ 并且 $\tau \left(f_4\to f\right)\ge \frac{1}{8}$ ，从而有 ${\omega }^{*}\left(f\right)\ge \frac{1}{4}+2\cdot \frac{1}{8}-\frac{1}{2}=0$ 。

情况 6 假设 $k\left(f\right)=4$ 。对于 $i=1,2,3,4,5$ ，令 $v_i$ 为坏3-点，此时 $u_1,u_3,u_5$ 为大点且 $v_6$ 为小点。根据断言3， $v_6$ 为 $5^{+}$ -点，因此 $\tau \left(v_6\to f\right)\ge \frac{11}{12}$ ，从而我们可得 ${\omega }^{*}\left(f\right)\ge \frac{11}{12}-\frac{5}{8}-\frac{1}{4}>0$ 。

基金项目

本文工作受到了浙江师范大学启航奖学金的资助。

文章引用

俞伟强. 平面图的(F, F_d)-分解问题
Vertex Partitions of Graphs into a Forest and a Forest with Bounded Maximum Degree[J]. 应用数学进展, 2019, 08(07): 1291-1298. https://doi.org/10.12677/AAM.2019.87151

参考文献