平面图的(F, Fd)-分解问题
Vertex Partitions of Graphs into a Forest and a Forest with Bounded Maximum Degree
DOI: 10.12677/AAM.2019.87151, PDF, HTML, XML, 下载: 1,166  浏览: 1,435  科研立项经费支持
作者: 俞伟强:浙江师范大学数学与计算机科学学院,浙江 金华
关键词: 顶点分解森林最大度Vertex Partition Forest Maximum Degree
摘要: 图G的(F, Fd)-分解是指将G的顶点集合划分为两个子集F和Fd,使得G[F]为森林,G[Fd]为最大度至多为d的森林。本文证明了每一个不含4-圈和5-圈的平面图都存在(F, Fd)-分解。
Abstract: An (F, Fd)-partition of a graph G is a vertex partition of its vertex set into subsets F and Fd such that G[F] is a forest, while G[Fd] 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, Fd)-partition.
文章引用:俞伟强. 平面图的(F, Fd)-分解问题[J]. 应用数学进展, 2019, 8(7): 1291-1298. https://doi.org/10.12677/AAM.2019.87151

1. 引言

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

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

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

本文证明了如下结果:

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

接下来给出文中的一些基本记号。G中点v的度数用 d G ( v ) 表示。我们分别用k-点, k + -点和 k -点表示度为k的点,度至少为k的点和度至多为k的点。同理定义k-面, k + -面和 k -面。称G中的 8 + -点为大点,否则为小点。因此v的 8 + -邻点称为大邻点,否则称为小邻点。称v在F中的邻点为F-邻点。用 n b ( v ) 表示v的大邻点的个数。对于 f F ( G ) ,若f的边界点按顺时针方向排列依次为 v 1 , v 2 , , v n ,则可记作 f = [ v 1 v 2 v n ] 。并且令 f i 表示以 v i v i + 1 为公共边与f相邻的面,其中 i = 1 , 2 , , n 且i对n取模。对于m-面 f = [ v 1 v 2 v m ] ,若 v i 的度数为 a i ,则可记f为 ( a 1 , a 2 , , a m ) -面。假设v为k-点,令 v 1 , v 2 , , v k 为按顺时针方向排列的邻点,则 g i 表示以 v v i v v i + 1 为边界与v关联的面,其中 i = 1 , 2 , , k 且i对k取模。

对于集合 S V ,令 G S 表示在G中删去所有的S中的点及其关联的边所得的图。对于与V不交的点集S,令 G + S 表示在G中加上S中的点所得的图。对于与E不交的边集 E ,令 G + E 表示在G中加上 E 中的边所得的图。

2. 定理证明

2.1. 极小反例的结构性质

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

断言 1 G中不存在 2 -点。

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

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

证明 假设 d ( v ) = 3 且它的邻点都为小点,即 7 -点。根据G的极小性可得, G v 存在 ( F , F 5 ) -分解。如果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的 ( F , F 5 ) -分解,矛盾。

断言 3 G中不存在6-面 f = [ v 1 v 2 v 6 ] 使得 f 1 , f 2 , f 3 是三角形,且 d ( v i ) = 3 i = 1 , 2 , , 6 ,或当 v 1 只有一个大邻点时, d ( v 1 ) = 4 d ( v i ) = 3 i = 2 , 3 , , 6

证明 不妨设 f = [ v 1 , v 2 , , v 6 ] 为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 = G { v 1 , v 2 , v 3 , v 4 , v 5 , v 6 } + { w 1 , w 2 , w 3 } + { w 1 w 2 , w 2 w 3 , w 3 w 1 , w 1 u 1 , w 2 u 2 , w 3 u 3 } ,则 G 中不存在4-圈和5-圈。由G的极小性可得,G存在 ( F , F 5 ) -分解。我们要证明在下列所有情况下我们都可以得到G的 ( F , F 5 ) -分解。在下列情形中,若 u 4 F 5 中,则将 v 1 放入 F 5 可能会增加 G [ F 5 ] 中点的度数,此时因为 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 [ { w 1 , w 2 , w 3 } ] G 中的三角形,则至少有一个点在 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都存在 ( F , F 5 ) -分解,矛盾。

断言 4 若 f = [ v 1 v 2 v 6 ] ( 3 , 3 , 3 , 3 , 3 , 8 + ) -面, f 3 , f 5 , f 6 为三角形,且与 f 5 , f 6 关联的第三个点为小点,则 d ( v 6 ) 9

证明 设 f = [ v 1 v 2 v 6 ] 为上述6-面,令 v 2 的第三个邻点和与 f 3 , f 5 , f 6 关联的第三个点分别为 u 1 , u 2 , u 3 , u 4 。令 G = G { v 2 } ,则由G的极小性, G 存在 ( F , F 5 ) -分解。当 d ( v 6 ) = 8 时,我们可以很容易地将 G ( F , F 5 ) -分解扩充到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 ( v 6 ) = 8 ,则 v 6 至多有四个 F 5 -邻点。因此我们可以将 v 1 或者 v 5 放入 F 5 v 2 放入F。因此我们总能得到G的 ( F , F 5 ) -分解,矛盾。

断言 5 设 f = [ v 1 v 2 v 6 ] 为G中的 ( 3 , 8 + , 3 , 3 , 8 + 3 ) -面,其中 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 = G { v 1 , v 6 } ,由G的极小性可得, G 存在 ( F , F 5 ) -分解。下面我们要证明G存在 ( F , F 5 ) -分解,从而得出矛盾,从而证明 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 ( v 2 ) = 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中的顶点和边定义初始权函数 ω 。对于 v V ( G ) ω ( v ) = 2 d ( v ) 6 ;对于 f F ( G ) ω ( f ) = d ( f ) 6 。根据欧拉公式和握手定理可得

v V ( G ) ( 2 d ( v ) 6 ) + f F ( G ) ( d ( f ) 6 ) = 12

然后定义适当的权规则将初始权 ω 通过权转移变为最终权 ω * ,使得对于每个 x V ( G ) F ( G ) ,有 ω * ( x ) 0 。注意到权转移过程不会改变总的权和,因此我们可以得出如下矛盾, 0 x V ( G ) F ( G ) ω * ( x ) = x V ( G ) F ( G ) ω ( x ) = 12 ,从而完成定理的证明。

d ( v ) = 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 = [ v 1 v 2 v 6 ] 是一个6-面,若 f i 是一个三角形,则令 u i 为与 f i 关联的第三个点。

若v是一个3-点,关联一个三角形且只有一个大邻点,则称v为一个坏3-点。另外,若v是一个4-点且关联两个三角形,则称v为坏4-点。设 f = [ v 1 v 2 v 6 ] 是一个 ( 3 , 8 + , 3 , 3 , 8 + , 3 ) -面且 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 V ( G ) F ( G ) ,我们用 τ ( x y ) 表示x转给y的权值。另外,用 l ( v ) 表示与v关联的三角形的个数。对于任意 f F ( G ) ,用 k ( f ) 表示与f关联的坏3-面的个数。我们的权规则定义如下:

(R1) 令 d ( v ) = 3 。若 l ( v ) = 0 ,则v给每个关联的6+-面转权 n b ( v ) 4 。设 l ( v ) = 1 ,若v是一个坏3-点,则v给每个关联的三角形转权1。否则,v给每个关联的三角形转权1,给每个关联的6+-面转权 3 n b ( v ) 4 8

(R2) 令 d ( v ) = 4 。若 l ( v ) = 0 ,则v给每个关联的 6 + -面转权 3 n b ( v ) + 8 16 。当 l ( v ) = 1 时,令 f i 为三角形,则 τ ( v f i ) = 1 τ ( v f 2 ) = τ ( v f 4 ) = 3 n b ( v ) + 2 8 τ ( v f 3 ) = 1 2 。设 l ( v ) = 2 ,则v给每个关联的三角形转权1,给每个关联的 6 + -面转权 3 n b ( v ) 8

(R3) 5-点给每个关联的三角形转权1,给每个关联的 6 + -面转权 n b ( v ) + 2 3

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

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

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

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

(R6) 6 + -面给每个关联的坏3-点转权 1 8 ,给每个相邻的坏6-面转权 1 8

下面我们证明对于所有 x V ( G ) F ( G ) ω * ( x ) 0 。令 v V ( G ) ,则 d ( v ) 3

· 设 d ( v ) = 3 。若 l ( v ) = 0 ,则由(R1)和(R5)可得 ω * ( v ) 3 4 n b ( v ) 3 n b ( v ) 4 0 。若 l ( v ) = 1 ,假设v是一个坏3-点,则根据规则(R1),(R5)和(R6)我们可以得出 ω * ( v ) 1 3 4 2 1 8 0 。否则, ω * ( v ) 1 2 3 n b ( v ) 4 8 + 3 n b ( v ) 4 0

· 设 d ( v ) = 4 。若 l ( v ) = 0 ,则由(R2)和(R5)可得 ω * ( v ) 3 n b ( v ) 4 + 2 4 3 n b ( v ) + 8 16 0 。若 l ( v ) = 1 ,则 ω * ( v ) 3 n b ( v ) 4 + 2 1 2 3 n b ( v ) + 2 8 1 2 0 。设 l ( v ) = 2 ,则 ω * ( v ) 3 n b ( v ) 4 + 2 2 2 3 n b ( v ) 8 0

· 设 d ( v ) = 5 ,由(R3)我们可以得到 ω * ( v ) 4 + n b ( v ) 2 3 n b ( v ) + 2 3 0

· 设 6 d ( v ) 7 ,由(R4)我们可以得到 ω * ( v ) 2 d ( v ) 6 d ( v ) 0

· 设 d ( v ) = 8 ,由(R5)我们可以得到 ω * ( v ) 2 8 6 8 3 4 4 0

· 设 d ( v ) 9 。如果 d ( v ) = 9 ,则根据(R5)可得 ω * ( v ) 12 9 3 4 5 1 4 4 = 0 。如果 d ( v ) 10 ,则根据(R5)可得 ω * ( v ) 2 d ( v ) 6 d ( v ) 2 3 d ( v ) 4 1 4 ( d ( v ) 2 + 1 ) 0

下面我们证明对于 f F ( G ) ,有 ω * ( f ) 0 。如果 d ( f ) = 3 ,那么根据规则(R1)-(R5)我们可以得出 ω * ( f ) 3 + 3 = 0 。如果 d ( f ) = 7 ,则f的边界上至多有6个坏3-点并且f至多相邻两个坏6-面。因此

ω * ( f ) 1 6 1 8 2 1 8 = 0 。设 d ( f ) 8 ,有 ω * ( f ) d ( f ) 6 1 8 d ( f ) 1 8 1 2 d ( f ) > 0 。现在假设 d ( f ) = 6 ,令 f = [ v 1 v 2 v 6 ] 。接下来我们将根据 k ( f ) 的值将证明分为以下几个部分。注意到不是坏3-点的3-点和小 4 + -点至少给每个关联的 6 + -面转权 1 4

情况 1 假设 k ( f ) = 0 ,则有 ω * ( f ) = ω ( f ) = d ( f ) 6 = 0

情况 2 假设 k ( f ) = 1 ,则f不相邻坏6-面。令 v 1 为坏3-点, f 1 为三角形。则 f 6 一定为 4 + -面。因此不管 v 6 是大点还是小点,都有 τ ( v 6 f ) 1 4 。从而有 ω * ( f ) 1 8 + 1 4 > 0

情况 3 假设 k ( f ) = 2

首先假设 v 1 , v 2 为坏3-点。如果 f 1 为三角形,那么 f 2 , f 6 都为 4 + -面,因此 τ ( v 3 f ) 1 4 τ ( v 6 f ) 1 4 。故有 ω * ( f ) 2 1 4 2 1 8 > 0 。现在假设 f 2 , f 6 为三角形,如果 v 3 为小点,那么 u 2 肯定为大点,因此根据规则(R1)-(R4)可得 τ ( v 3 f ) 3 8 。从而有 ω * ( f ) 3 8 2 1 8 1 8 = 0 。假设 v 3 为大点,如果 v 4 也为大点,则根据规则(R5.1)可得 τ ( v 3 f ) 3 8 ;否则 τ ( v 4 f ) 1 4 。由对称性可得 τ ( v 5 f ) + τ ( v 6 f ) 1 4 。因此 ω * ( f ) 2 1 4 2 1 8 > 0

假设 v 1 , v 3 为坏3-点。如果 f 1 , f 2 为三角形,那么 f 3 , f 6 都为 4 + -面,因此有 τ ( v 4 f ) 1 4 τ ( v 6 f ) 1 4 ,故 ω * ( f ) 2 1 4 2 1 8 > 0 。现在假设 f 3 , f 6 为三角形,由于 f 1 , f 2 4 + -面且 v 2 不为坏点,因此 τ ( v 2 f ) 1 4 ,故 ω * ( f ) 1 4 2 1 8 = 0 。根据对称性我们假设 f 1 , f 3 为三角形,那么 v 2 必为 4 + -点且不为坏点,因此 ω * ( f ) 1 4 2 1 8 = 0

假设 v 1 , v 4 为坏3-点。由对称性,如果 f 1 , f 3 为三角形,那么 f 4 , f 6 必为 4 + -面。由于 v 5 , v 6 都不为坏点,因此 τ ( v 5 f ) 1 4 τ ( v 6 f ) 1 4 。故 ω * ( f ) 2 1 4 2 1 8 > 0 。如果 f 1 , f 4 为三角形,那么 f 3 , f 6 4 + -面,同样我们有 τ ( v 3 f ) 1 4 τ ( v 6 f ) 1 4 。因此 ω * ( f ) 2 1 4 2 1 8 > 0

情况 4 假设 k ( f ) = 3

假设 v 1 , v 2 , v 3 为坏3-点。根据对称性假设 f 1 , f 3 为三角形,则有 τ ( v 6 f ) 1 4 。如果 v 4 为小点,那么 u 3 肯定为大点,因此根据(R2)-(R4)可得 τ ( v 4 f ) 1 4 。假设 v 4 为大点,如果 v 5 也是大点,那么根据规则(R5)有 τ ( v 4 f ) 3 8 。否则 τ ( v 5 f ) 1 4 。因此 ω * ( f ) 2 1 4 3 1 8 1 8 = 0

假设 v 1 , v 2 , v 4 为坏3-点。如果 f 1 , f 3 为三角形,那么根据以上讨论我们可得 τ ( v 5 f ) 1 4 τ ( v 6 f ) 1 4 。因此 ω * ( f ) 2 1 4 3 1 8 > 0 。假设 f 1 , f 4 为三角形,同样可得 τ ( v 3 f ) 1 4 τ ( v 6 f ) 1 4 。因此 ω * ( f ) 2 1 4 3 1 8 > 0 。假设 f 2 , f 3 , f 6 为三角形。如果 v 3 为小点,那么 u 2 肯定为大点,因此根据规则(R2), τ ( v 3 f ) 3 8 。由于 f 4 4 + -面, v 5 不为坏点,因此 τ ( v 5 f ) 1 4 ,故 ω * ( f ) 1 4 + 3 8 3 1 8 > 0 。现在假设 v 3 为大点,那么 v 5 肯定为小点。同样有 τ ( v 5 f ) 1 4 。如果 v 6 为小点,那么 u 6 肯定为大点,因此根据规则(R2), τ ( v 6 f ) 3 8 。否则假设 v 6 为大点,如果 f 5 为三角形,那么根据规则(R2)有 τ ( v 5 f ) 5 8 ,或根据规则(R5)有 τ ( v 6 f ) 1 4 。在每种情况下我们都有 ω * ( f ) 2 1 4 3 1 8 1 8 = 0 。最后假设 f 2 , f 4 , f 6 为三角形。此时 v 3 4 + -点且 f 3 4 + -面。如果 v 3 为小点,那么 u 2 肯定为大点,因此根据规则(R2), τ ( v 3 f ) 5 8 。现在假设 v 3 为大点,由于f为 4 + -面, τ ( v 3 f ) 1 4 。并且 v 5 为小点,那么 u 6 肯定为大点,因此根据规则(R2), τ ( v 6 f ) 5 8 。否则 τ ( v 5 f ) 3 8 。因此总有 ω * ( f ) 5 8 3 8 1 8 > 0

假设 v 1 , v 3 , v 5 为坏3-点。首先假设 f 1 , f 2 , f 4 为三角形,则 f 3 , f 5 , f 6 必为 4 + -面,因此 τ ( v 6 f ) 1 4 τ ( v 4 f ) 1 4 。故 ω * ( f ) 2 1 4 3 8 > 0 。现在假设 f 1 , f 3 , f 5 为三角形,同样可得 τ ( v 2 f ) 1 4 τ ( v 4 f ) 1 4 。因此 ω * ( f ) 2 1 4 3 8 > 0

情况 5 假设 k ( f ) = 4

假设 v 1 , v 2 , v 3 , v 4 为坏3-点。首先假设 f 1 , f 3 为三角形,那么f不相邻坏6-面。并且 f 4 , f 6 都为 4 + -面,因此 τ ( v 5 f ) 1 4 τ ( v 6 f ) 1 4 。故 ω * ( f ) 2 1 4 4 1 8 > 0 。现在假设 f 2 , f 4 , f 6 为三角形,如果 v 5 , v 6 都为大点,那么 τ ( v 5 f ) 1 4 τ ( v 6 f ) 1 4 。如果 v 5 , v 6 都为小点,那么 u 4 , u 6 都为大点,因此根据规则(R2)同样有 τ ( v 5 f ) 1 4 τ ( v 6 f ) 1 4 。否则根据对称性假设 v 5 为大点而 v 6 为小点,此时 u 6 肯定为大点,因此 τ ( v 6 f ) 3 4 。故 ω * ( f ) 3 4 4 1 8 2 1 8 = 0

假设 v 1 , v 2 , v 3 , v 5 为坏3-点。首先假设 f 1 , f 3 , f 4 为三角形,那么 f 5 , f 6 肯定为 4 + -面,因此根据规则(R1), τ ( v 6 f ) 1 4 。此时如果 v 4 为小点,那么 u 3 , u 4 肯定为大点,因此根据(R3) τ ( v 4 f ) 2 3 ,故 ω * ( f ) 1 4 + 2 3 1 2 1 8 > 0 。现在假设 v 4 为大点,根据断言4, d ( v 4 ) 9 ,此外 f 2 不为坏面,因此 τ ( v 4 f ) 1 4 。从而有 ω * ( f ) 2 1 4 1 2 = 0 。假设 f 2 , f 4 , f 6 为三角形,那么 f 3 , f 5 肯定为 4 + -面且 v 4 为小 4 + -点,因此 τ ( v 4 f ) 1 4 。此时如果 v 6 为大点,那么 f 1 肯定不为坏面且 τ ( v 6 f ) 1 4 ,因此 ω * ( f ) 2 1 4 1 2 = 0 。否则 u 6 肯定为大点,因此根据规则(R2), τ ( v 6 f ) 5 8 。从而有 ω * ( f ) 5 8 + 1 4 1 2 1 8 > 0

假设 v 1 , v 2 , v 4 , v 5 为坏3-点。首先假设 f 1 , f 4 为三角形,那么f相邻的其余面都为 4 + -面,此时有 τ ( v 3 f ) 1 4 τ ( v 6 f ) 1 4 。因此 ω * ( f ) 2 1 4 1 2 = 0 。假设 f 1 , f 3 , f 5 为三角形,那么此时 f 2 , f 6 4 + -面。如果 v 3 , v 6 都为大点,那么 ω * ( f ) 2 1 4 1 2 = 0 。否则 v 3 , v 6 都为小点并且 u 3 , u 5 都为大点,因此根据规则(R2), τ ( v 3 f ) 5 8 ,故 ω * ( f ) 5 8 1 2 > 0 。最后假设 f 2 , f 3 , f 5 , f 6 为三角形,如果 v 3 , v 6 都为小点,那么对于 i = 2 , 3 , 5 , 6 u i 都为大点。根据规则(R3), τ ( v 3 f ) 2 3 τ ( v 6 f ) 2 3 ,因此 ω * ( f ) 2 2 3 1 2 2 1 8 > 0 。现在假设 v 3 , v 6 中恰有一个为小点,不妨设为 v 3 ,此时 f 1 , f 4 不为坏面,因此我们同样可得 τ ( v 3 f ) 2 3 ω * ( f ) 2 3 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 + -点。因此 ω * ( f ) 2 1 4 1 2 = 0 。否则f为坏6-面,同样根据断言5, v 3 , v 6 中至少有一个点为 9 + -点,因此根据规则(R6), τ ( f 1 f ) 1 8 并且 τ ( f 4 f ) 1 8 ,从而有 ω * ( f ) 1 4 + 2 1 8 1 2 = 0

情况 6 假设 k ( f ) = 4 。对于 i = 1 , 2 , 3 , 4 , 5 ,令 v i 为坏3-点,此时 u 1 , u 3 , u 5 为大点且 v 6 为小点。根据断言3, v 6 5 + -点,因此 τ ( v 6 f ) 11 12 ,从而我们可得 ω * ( f ) 11 12 5 8 1 4 > 0

基金项目

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

参考文献

[1] Appel, K. and Haken, W. (1977) Every Planar Map Is Four Colorable. Part I: Discharging. Illinois Journal of Mathematics, 21, 429-490.
https://doi.org/10.1215/ijm/1256049011
[2] Appel, K. and Haken, W. (1977) Every Planar Map Is Four Colorable. Part II: Reducibility. Illinois Journal of Mathematics, 21, 491-567.
https://doi.org/10.1215/ijm/1256049012
[3] Borodin, O.V. (1976) A Proof of Grunbaum’s Conjecture on the Acyclic 5-Colorability of Planar Graphs (Russian). Doklady Akademii nauk SSSR, 231, 18-20.
[4] Poh, K.S. (1990) On the Linear Vertex-Arboricity of a Plane Graph. Journal of Graph Theory, 14, 73-75.
https://doi.org/10.1002/jgt.3190140108
[5] Chartrand, G. and Kronk, H.V. (1969) The Point-Arboricity of Planar Graphs. Journal of the London Mathematical Society, 1, 612-616.
https://doi.org/10.1112/jlms/s1-44.1.612
[6] Raspaud, A. and Wang, W. (2011) On the Vertex-Arboricity of Planar Graphs. European Journal of Combinatorics, 52, 1004-1010.
[7] Chen, M. and Raspaud, A. (2012) Vertex-Arboricity of Planar Graphs without Intersecting Triangles. European Journal of Combinatorics, 33, 905-923.
https://doi.org/10.1016/j.ejc.2011.09.017
[8] Dross, F. and Montassier, M. (2015) Partitioning a Triangle-Free Planar Graph into a Forest and a Forest of Bounded Degree. Electronic Notes in Discrete Mathematics, 49, 269-275.
https://doi.org/10.1016/j.endm.2015.06.037