期刊菜单

Polychromatic Colorings of Some Plane Graphs
DOI: 10.12677/AAM.2019.87148, PDF, HTML, XML, 下载: 1,040  浏览: 1,550

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).

1. 引言

$p\left(g\right)=\mathrm{min}\left\{p\left(G\right)|g\left(G\right)=g\right\}$

$⌊\frac{3g-5}{4}⌋\le p\left(g\right)\le ⌊\frac{3g+1}{4}⌋$

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

2. 简化对偶图的构造

1) 定义点集 $V\left(H\right)=F\left(G\right)$ ，即G的每个面对应H的每个点；

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

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

3. 主要结果

$p\left(g\right)\ge ⌊\frac{3g-5+{w}_{1}+{w}_{2}}{4}⌋$${w}_{i}=\mathrm{min}\left\{w\left(e\right)|e\in {E}_{i}\right\}$

$p\left(G\right)\ge ⌊\frac{3\left(g-{w}_{1}-{w}_{2}\right)-5}{4}⌋+{w}_{1}+{w}_{2}=⌊\frac{3\left(g-{w}_{1}-{w}_{2}\right)-5}{4}+\frac{4\left({w}_{1}+{w}_{2}\right)}{4}⌋=⌊\frac{3g-5+{w}_{1}+{w}_{2}}{4}⌋$

$p\left(g\right)\ge ⌊\frac{3g-5+w}{4}⌋$ 其中 $w=\underset{0\le i\le 2k}{\mathrm{max}}\left\{\mathrm{min}\left\{w\left({v}_{i}\right),w\left(e\right)|e\in {E}_{i}\right\}\right\}$

${g}_{i}\left({v}_{i}\right)=g\left({v}_{i}\right)-2{w}_{i}=g-{w}_{i}+g\left({v}_{i}\right)-g-{w}_{i}\ge g-{w}_{i}$

$p\left(g\right)\ge ⌊\frac{3g-5+{w}_{s}}{4}⌋$

${w}_{s}\le w\left({v}_{0}\right)=⌊\frac{g\left({v}_{0}\right)-g}{{d}_{H}\left({v}_{0}\right)-1}⌋=⌊\frac{g\left({v}_{0}\right)-g}{n-1}⌋$${g}^{\prime }\left({v}_{0}\right)=g\left({v}_{0}\right)-n{w}_{s}\text{ }=g-{w}_{s}\text{ }+g\left({v}_{0}\right)-g-\left(n-1\right){w}_{s}\text{ }\ge g-{w}_{s}$ ，所以G中规模最小的面在 ${G}^{\prime }$ 中仍然规模最小，所以 $g\left({G}^{\prime }\right)=g-{w}_{s}$ 。由定理1.1可给出 ${G}^{\prime }$$⌊\frac{3\left(g-{w}_{s}\right)-5}{4}⌋$ 种颜色的多色染色 ${\phi }^{\prime }$ 。将 ${G}^{\prime }$ 恢复为G，基于 ${\phi }^{\prime }$ 染色得到G的部分染色 $\phi$ 。注意到G中除 ${v}_{0}$ 以外的面上恰有 ${w}_{s}$ 个2-点未染色，( ${v}_{0}$ 对应面上有 $n{w}_{s}$ 个2-点未染色)，现在用不同于 $\phi$ 中的 ${w}_{s}$ 种新颜色去染每个面上的未染色点，则每个面上可以出现这 ${w}_{s}$ 种新颜色，容易看出 ${v}_{0}$ 对应面上这 ${w}_{s}$ 种新颜色各出现n次。显然 $p\left(G\right)\ge ⌊\frac{3\left(g-{w}_{s}\right)-5}{4}⌋+{w}_{s}=⌊\frac{3g-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