Advances in Applied Mathematics
Vol.
08
No.
07
(
2019
), Article ID:
31441
,
5
pages
10.12677/AAM.2019.87148
Polychromatic Colorings of Some Plane Graphs
Shizhen Zhang
School of Mathematics and Statistics, Shandong Normal University, Jinan Shandong
Received: July 4th, 2019; accepted: July 19th, 2019; published: July 26th, 2019
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 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 to , where w is the sum of weights for disjoint edge covers of H(G).
Keywords:Planar Graphs, Polychromatic Coloring, Guarding Problems
一类平面图的多色染色问题
张世桢
山东师范大学数学与统计学院,山东 济南
收稿日期:2019年7月4日;录用日期:2019年7月19日;发布日期:2019年7月26日
摘 要
一个平面图G的一个多色k-染色是一个k种颜色的点染色,每一种颜色都会出现在每个面的边界上。最大的非负整数k称为G的多色染色数,记为p(G)。2009年Alon等人证明了每个平面图都有多色染色数 ,其中g是G的最小面的规模。以平面图G的简化对偶图H(G)为基础,我们讨论了当H(G)为一个偶圈、奇圈、星时将下界 提高成 的形式,其中w是H(G)的不相交的边覆盖的权重之和。
关键词 :平面图,多色染色,保护问题
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为一个平面图,其点集、边集和面集分别记为 、 和 。一个面f的规模是它的边界上的顶点数,记为 。 定义为这个图G中最小面的规模: 。图G的顶点的k-染色是一种映射 。如果任意两个相邻的点染不同颜色则称 为正常染色。如果所有k种颜色都出现在一个面 上,则称这个面为多色的。如果一个顶点的k-染色 使得G的每个面都是多色的,则称 为图G的一个多色k-染色。G的多色染色数p(G)是使得G存在多色k-染色时最大的k。对于任意的平面图G,定义:
很显然对任意的平面图G都有 。1969年Lovász [1] 证明了每个简单平面图G都有 。1999年Mohar和Škrekovski [2] 使用四色定理对Lovász的结果给出了另一种证明。2009年Alon等人 [3] 给出了对于一般平面图的多色染色数的上下界。
定理1.1 [3] , ,当 时,
从定理1.1可以看出,当 时 的取值范围是2个或者3个整数。
平面图的多色染色在组合学和计算几何中有着很多应用,以下是1975年Chvátal [4] 提出并且证明的艺术画廊定理。
定理1.2 [4] 设P是一个有n个顶点的多边形,则 个顶点足够用来保护P。
定理1.2说明在P中存在一个含有 个点的点集S,使得S中的点可以监测到整个多边形P的面,此时称为S保护P,S称为保护集。保护问题与多色染色问题有着密切联系。对于平面图G,寻找最小的点集S使得G的每个面都与S中至少一个点关联。其实G的多色染色中每种颜色对应的点集是一个保护集,因为每种颜色都会出现在所有面上,每种颜色对应的点共同保护了G。
2012年Horev等人 [5] 研究了最大度3的二部图的多色4-染色问题并证明了以下定理:
定理1.3 [5] 最大度3的二部图是正常多色4-可染的。
如果存在一个平面嵌入使得图中所有顶点都属于外平面,则这样的平面图称为外平面图。在外平面图中最小面的规模等于最小圈的长度(围长)。以下定理表明了对于 的外平面图多色染色数的非平凡上界 是紧的。
定理1.4 [3] 设G是一个外平面图且满足 ,则G存在一种使用g种颜色的多色正常染色。
通过上面的结果我们可以看到对于一些类别的图可以将多色染色数 提高到g,而通过定理1.1可知 的范围由g唯一决定,现在我们考虑一类平面图,在这类图中可以将多色染色数的下界 提高。
考虑一类含有较多二度点的平面图,这些二度点在两个面的共同边界上,这些点染上的颜色会同时出现在两个面上。若能在一个平面图G的每个面的边界上收缩w个二度点,则在所得平面图 中最小面的规模减小为 ,根据定理1.1可知此时 。再将之前每个面上收缩的w个二度点恢复,并且将这些点染w种不同颜色,这样每个面都增加了种新颜色,从而 。当 时这个下界严格高于 ,部分改进了定理1.1
的下界。
2. 简化对偶图的构造
定义2.1 设G是含有较多二度点的平面图,我们定义简化对偶图 :
1) 定义点集 ,即G的每个面对应H的每个点;
2) 定义边集E(H) = {uv |面u与面v有公共的边界路},即这两个面的公共边界上有二度点。特别地,如果两个平面的公共边界上有多条边界路,在简化对偶图中对应两点也只有一条边。显然H的边对应的是原图中两个面公共的边界路;
3) 设e为H中的边,定义边的权重w(e)为e连接的两个点对应的面上公共的二度点数。
这样定义的简化对偶图H也是简单平面图。
若H的边集E(H)的子集 满足 ,即 中的边可以包含H的所有点,则称 为H的一个边覆盖。
3. 主要结果
定理3.1 假设G是一个平面图,最小面的规模为g,H = H(G)是它的简化对偶图。如果H是一个偶圈,则E(H)可以分解成两个不相交的匹配 和 ,并且
, 。
证明 设 ,则H有2个不相交的匹配 和 。令 , 。在 中每条边对应公共边界路上去掉任意 个2-点,再在 中每条边对应公共边界路上去掉任意 个2-点,得到平面图 , 。根据定理1.1,可给出 的 种颜色的多色染色 ,再将 恢复为G,基于染色 得到G的部分染色 。注意到G的每个面上恰有 个2-点未染色,现在用不同于 中的 个新颜色去染每个面上的未染色点,则每个面上可以出现这 个新颜色。显然有
定义3.2 设v是H中的点且 ,v在原图中对应的面规模为g(v),定义点权 。
定理3.3 假设G是一个平面图,最小面的规模为g, 是它的简化对偶图。如果H是一个奇圈, ,则 有2k + 1个不同的最小边覆盖 ( ),并且
其中 。
证明 设 ,则 有2k + 1个不同的最小边覆盖 ( )。对任意 ,点 对应的H的最小边覆盖记为 (下标模2k + 1),令 。对每个 都可进行下列操作:在图G中对 中每条边对应的公共边界路上去掉任意 个2-点,得到平面图 。面v在 中的规模记为 ,对于任意的 , 。对于面 :由 ,有
,
所以G中规模最小的面在 中仍然规模最小,所以 。由定理1.1可给出 的 种颜色的多色染色 。将 恢复为G,基于 染色得到G的部分染色 。注意到G中除 以外的面上恰有 个2-点未染色,( 对应面上有 个2-点未染色),现在用不同于 中的 种新颜色去染每个面上的未染色点,则每个面上可以出现这 种新颜色,容易看出 对应面上这 种新颜色各出现2次。显然 。对所有 ,令 ,显然有 。
定理3.4 假设G是一个平面图,最小面的规模为g, 是它的简化对偶图。如果H是一个星, 是星的中心点,令 ,则
。
证明 设 ,存在唯一的边覆盖 ,星中心点 满足 。在 中每条边对应的公共边界路上去掉任意 个2-点,得到平面图 。面v在 中的规模记为 ,对于任意的 , 。对于面 :
由 , ,所以G中规模最小的面在 中仍然规模最小,所以 。由定理1.1可给出 的 种颜色的多色染色 。将 恢复为G,基于 染色得到G的部分染色 。注意到G中除 以外的面上恰有 个2-点未染色,( 对应面上有 个2-点未染色),现在用不同于 中的 种新颜色去染每个面上的未染色点,则每个面上可以出现这 种新颜色,容易看出 对应面上这 种新颜色各出现n次。显然 。
致谢
在论文完成之际我要特别感谢我的导师张霞副教授。本文是在张霞副教授的悉心指导和严格要求下完成的,她对文章的每个章节和字词都仔细检查和指导,付出了自己的大量时间,她严肃的科研态度、严谨的治学精神、精益求精的工作作风一直激励着我,督促我不断改进自身不足和探索进取。在此我向我的导师致以深深的谢意。最后我向各位尊敬的评审专家致以最诚挚的感谢,谢谢你们对本论文做出的评审以及提出的宝贵意见。
文章引用
张世桢. 一类平面图的多色染色问题
Polychromatic Colorings of Some Plane Graphs[J]. 应用数学进展, 2019, 08(07): 1272-1276. https://doi.org/10.12677/AAM.2019.87148
参考文献
- 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