一类平面图的多色染色问题
Polychromatic Colorings of Some Plane Graphs
DOI: 10.12677/AAM.2019.87148, PDF, HTML, XML, 下载: 1,040  浏览: 1,550 
作者: 张世桢:山东师范大学数学与统计学院,山东 济南
关键词: 平面图多色染色保护问题Planar Graphs Polychromatic Coloring Guarding Problems
摘要: 一个平面图G的一个多色k-染色是一个k种颜色的点染色,每一种颜色都会出现在每个面的边界上。最大的非负整数k称为G的多色染色数,记为p(G)。2009年Alon等人证明了每个平面图都有多色染色数 p(G)≥⌊(3g-5)/4⌋,其中g是G的最小面的规模。以平面图G的简化对偶图H(G)为基础,我们讨论了当H(G)为一个偶圈、奇圈、星时将下界⌊(3g-5)/4⌋提高成⌊(3g-5+w)/4⌋ 的形式,其中w是H(G)的不相交的边覆盖的权重之和。
Abstract: A k-polychromatic coloring of a plane graph G is a vertex coloring of G with k colors in such a way that each color appears on the boundary of each face. The maximum nonnegative integer k is called the polychromatic number of G and denoted by p(G). In 2009, Alon et al. proved that each plane graph has p(G)≥⌊(3g-5)/4⌋  colors, where g is the minimum face size of G. Basing on the simplified dual graph H(G) of a plane graph G, we discuss some cases for that H(G) is an even cycle, an odd cycle or a star and improve the lower bound ⌊(3g-5)/4⌋  to ⌊(3g-5+w)/4⌋ , where w is the sum of weights for disjoint edge covers of H(G).
文章引用:张世桢. 一类平面图的多色染色问题[J]. 应用数学进展, 2019, 8(7): 1272-1276. https://doi.org/10.12677/AAM.2019.87148

1. 引言

在这篇文章中我们只考虑无向有限简单图。平面图是指能够嵌入到平面内的图。设G为一个平面图,其点集、边集和面集分别记为 V ( G ) E ( G ) F ( G ) 。一个面f的规模是它的边界上的顶点数,记为 g ( f ) g ( G ) 定义为这个图G中最小面的规模: g ( G ) = min { g ( f ) | f F ( G ) } 。图G的顶点的k-染色是一种映射 φ : V ( G ) { 1 , , k } 。如果任意两个相邻的点染不同颜色则称 φ 为正常染色。如果所有k种颜色都出现在一个面 f F ( G ) 上,则称这个面为多色的。如果一个顶点的k-染色 φ 使得G的每个面都是多色的,则称 φ 为图G的一个多色k-染色。G的多色染色数p(G)是使得G存在多色k-染色时最大的k。对于任意的平面图G,定义:

p ( g ) = min { p ( G ) | g ( G ) = g }

很显然对任意的平面图G都有 p ( g ( G ) ) p ( G ) g ( G ) 。1969年Lovász [1] 证明了每个简单平面图G都有 p ( G ) 2 。1999年Mohar和Škrekovski [2] 使用四色定理对Lovász的结果给出了另一种证明。2009年Alon等人 [3] 给出了对于一般平面图的多色染色数的上下界。

定理1.1 [3] p ( 1 ) = p ( 2 ) = 1 p ( 3 ) = p ( 4 ) = 2 ,当 g 5 时,

3 g 5 4 p ( g ) 3 g + 1 4

从定理1.1可以看出,当 g 5 p ( g ) 的取值范围是2个或者3个整数。

平面图的多色染色在组合学和计算几何中有着很多应用,以下是1975年Chvátal [4] 提出并且证明的艺术画廊定理。

定理1.2 [4] 设P是一个有n个顶点的多边形,则 n / 3 个顶点足够用来保护P。

定理1.2说明在P中存在一个含有 n / 3 个点的点集S,使得S中的点可以监测到整个多边形P的面,此时称为S保护P,S称为保护集。保护问题与多色染色问题有着密切联系。对于平面图G,寻找最小的点集S使得G的每个面都与S中至少一个点关联。其实G的多色染色中每种颜色对应的点集是一个保护集,因为每种颜色都会出现在所有面上,每种颜色对应的点共同保护了G。

2012年Horev等人 [5] 研究了最大度3的二部图的多色4-染色问题并证明了以下定理:

定理1.3 [5] 最大度3的二部图是正常多色4-可染的。

如果存在一个平面嵌入使得图中所有顶点都属于外平面,则这样的平面图称为外平面图。在外平面图中最小面的规模等于最小圈的长度(围长)。以下定理表明了对于 g ( G ) 3 的外平面图多色染色数的非平凡上界 p ( G ) g ( G ) 是紧的。

定理1.4 [3] 设G是一个外平面图且满足 g = g ( G ) 3 ,则G存在一种使用g种颜色的多色正常染色。

通过上面的结果我们可以看到对于一些类别的图可以将多色染色数 p ( g ) 提高到g,而通过定理1.1可知 p ( g ) 的范围由g唯一决定,现在我们考虑一类平面图,在这类图中可以将多色染色数的下界 ( 3 g 5 ) / 4 提高。

考虑一类含有较多二度点的平面图,这些二度点在两个面的共同边界上,这些点染上的颜色会同时出现在两个面上。若能在一个平面图G的每个面的边界上收缩w个二度点,则在所得平面图 G 中最小面的规模减小为 g w ,根据定理1.1可知此时 p ( G ) 3 ( g w ) 5 4 。再将之前每个面上收缩的w个二度点恢复,并且将这些点染w种不同颜色,这样每个面都增加了种新颜色,从而 p ( G ) 3 ( g w ) 5 4 + w = 3 g 5 4 + w 4 。当 w 4 时这个下界严格高于 3 g 5 4 ,部分改进了定理1.1

的下界。

2. 简化对偶图的构造

定义2.1 设G是含有较多二度点的平面图,我们定义简化对偶图 H = H ( G ) = ( V ( H ) , E ( H ) )

1) 定义点集 V ( H ) = F ( G ) ,即G的每个面对应H的每个点;

2) 定义边集E(H) = {uv |面u与面v有公共的边界路},即这两个面的公共边界上有二度点。特别地,如果两个平面的公共边界上有多条边界路,在简化对偶图中对应两点也只有一条边。显然H的边对应的是原图中两个面公共的边界路;

3) 设e为H中的边,定义边的权重w(e)为e连接的两个点对应的面上公共的二度点数。

这样定义的简化对偶图H也是简单平面图。

若H的边集E(H)的子集 E i 满足 ,即 E i 中的边可以包含H的所有点,则称 E i 为H的一个边覆盖。

3. 主要结果

定理3.1 假设G是一个平面图,最小面的规模为g,H = H(G)是它的简化对偶图。如果H是一个偶圈,则E(H)可以分解成两个不相交的匹配 E 1 E 2 ,并且

p ( g ) 3 g 5 + w 1 + w 2 4 w i = min { w ( e ) | e E i }

证明 设 H = C 2 k = v 1 v 2 v 2 k v 1 ,则H有2个不相交的匹配 E 1 = { v 2 i 1 v 2 i | 1 i k } E 2 = { v 2 i v 2 i + 1 | 1 i k 1 } { v 2 k v 1 } 。令 w j = min { w ( e ) | e E j } j = 1 , 2 。在 E 1 中每条边对应公共边界路上去掉任意 w 1 个2-点,再在 E 2 中每条边对应公共边界路上去掉任意 w 2 个2-点,得到平面图 G g ( G ) = g w 1 w 2 。根据定理1.1,可给出 G 3 ( g w 1 w 2 ) 5 4 种颜色的多色染色 φ ,再将 G 恢复为G,基于染色 φ 得到G的部分染色 φ 。注意到G的每个面上恰有 w 1 + w 2 个2-点未染色,现在用不同于 φ 中的 w 1 + w 2 个新颜色去染每个面上的未染色点,则每个面上可以出现这 w 1 + w 2 个新颜色。显然有

p ( G ) 3 ( g w 1 w 2 ) 5 4 + w 1 + w 2 = 3 ( g w 1 w 2 ) 5 4 + 4 ( w 1 + w 2 ) 4 = 3 g 5 + w 1 + w 2 4

定义3.2 设v是H中的点且 d H ( v ) 2 ,v在原图中对应的面规模为g(v),定义点权 w ( v ) = g ( v ) g d H ( v ) 1

定理3.3 假设G是一个平面图,最小面的规模为g, H = H ( G ) 是它的简化对偶图。如果H是一个奇圈, H = C 2 k + 1 = v 0 v 1 v 2 k ,则 C 2 k + 1 有2k + 1个不同的最小边覆盖 E i ( 0 i 2 k ),并且

p ( g ) 3 g 5 + w 4 其中 w = max 0 i 2 k { min { w ( v i ) , w ( e ) | e E i } }

证明 设 H = C 2 k + 1 = v 0 v 1 v 2 k ,则 C 2 k + 1 有2k + 1个不同的最小边覆盖 E i ( 0 i 2 k )。对任意 0 i 2 k ,点 v i 对应的H的最小边覆盖记为 E i = { v i 1 v i , v i v i + 1 , v i + 2 j v i + 1 + 2 j , 1 j k 1 } (下标模2k + 1),令 w i = min { w ( v i ) , w ( e ) | e E i } 。对每个 E i 都可进行下列操作:在图G中对 E i 中每条边对应的公共边界路上去掉任意 w i 个2-点,得到平面图 G i 。面v在 G i 中的规模记为 g i ( v ) ,对于任意的 v v i g i ( v ) = g ( v ) w i 。对于面 v i :由 w i w ( v i ) = g ( v i ) g ,有

g i ( v i ) = g ( v i ) 2 w i = g w i + g ( v i ) g w i g w i

所以G中规模最小的面在 G i 中仍然规模最小,所以 g ( G i ) = g w i 。由定理1.1可给出 G i 3 ( g w i ) 5 4 种颜色的多色染色 φ i 。将 G i 恢复为G,基于 φ i 染色得到G的部分染色 φ 。注意到G中除 v i 以外的面上恰有 w i 个2-点未染色,( v i 对应面上有 2 w i 个2-点未染色),现在用不同于 φ 中的 w i 种新颜色去染每个面上的未染色点,则每个面上可以出现这 w i 种新颜色,容易看出 v i 对应面上这 w i 种新颜色各出现2次。显然 p ( G ) 3 ( g w i ) 5 4 + w i = 3 g 5 + w i 4 。对所有 E i ,令 w = max 0 i 2 k w i ,显然有 p ( G ) max 0 i 2 k 3 ( g 5 ) + w i 4 = 3 g 5 + w 4

定理3.4 假设G是一个平面图,最小面的规模为g, H = H ( G ) 是它的简化对偶图。如果H是一个星, v 0 是星的中心点,令 w s = min { w ( v 0 ) , w ( e i ) | e i e ( H ) } ,则

p ( g ) 3 g 5 + w s 4

证明 设 H = K 1 , n ,存在唯一的边覆盖 E 1 = E ( H ) ,星中心点 v 0 满足 d H ( v 0 ) = n > 1 。在 E 1 中每条边对应的公共边界路上去掉任意 w s 个2-点,得到平面图 G 。面v在 G 中的规模记为 g ( v ) ,对于任意的 v v 0 g ( v ) = g ( v ) w s 。对于面 v 0

w s w ( v 0 ) = g ( v 0 ) g d H ( v 0 ) 1 = g ( v 0 ) g n 1 g ( v 0 ) = g ( v 0 ) n w s = g w s + g ( v 0 ) g ( n 1 ) w s g w s ,所以G中规模最小的面在 G 中仍然规模最小,所以 g ( G ) = g w s 。由定理1.1可给出 G 3 ( g w s ) 5 4 种颜色的多色染色 φ 。将 G 恢复为G,基于 φ 染色得到G的部分染色 φ 。注意到G中除 v 0 以外的面上恰有 w s 个2-点未染色,( v 0 对应面上有 n w s 个2-点未染色),现在用不同于 φ 中的 w s 种新颜色去染每个面上的未染色点,则每个面上可以出现这 w s 种新颜色,容易看出 v 0 对应面上这 w s 种新颜色各出现n次。显然 p ( G ) 3 ( g w s ) 5 4 + w s = 3 g 5 + w s 4

致谢

在论文完成之际我要特别感谢我的导师张霞副教授。本文是在张霞副教授的悉心指导和严格要求下完成的,她对文章的每个章节和字词都仔细检查和指导,付出了自己的大量时间,她严肃的科研态度、严谨的治学精神、精益求精的工作作风一直激励着我,督促我不断改进自身不足和探索进取。在此我向我的导师致以深深的谢意。最后我向各位尊敬的评审专家致以最诚挚的感谢,谢谢你们对本论文做出的评审以及提出的宝贵意见。

参考文献

[1] Lovász, L. (1969 and 2007) Combinatorial Problems and Exercises. AMS Chelsea Publishing, Providence, Rhode Island.
https://doi.org/10.1090/chel/361
[2] Mohar, B. and Skrekovski, R. (1999) The Grötzsch Theorem for the Hypergraph of Maximal Cliques. The Electronic Journal of Combinatorics, 6, 1-13.
[3] Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B. and Zumstein, Ph. (2009) Polychromatic Colorings of Plane Graphs. Discrete Computational Geom-etry, 42, 421-442.
https://doi.org/10.1007/s00454-009-9171-5
[4] Chvátal, V. (1975) A Combinatorial Theorem in Plane Geometry. Journal of Combinatorial Theory (B), 18, 39-41.
https://doi.org/10.1016/0095-8956(75)90061-1
[5] Horev, E., Katz, M., Krakovski, R. and Nakamoto, A. (2012) Polychromatic 4-Coloring of Cubic Bipartite Plane Graphs. Discrete Mathematics, 312, 715-719.
https://doi.org/10.1016/j.disc.2011.11.016