一类平面图的多色染色问题

Polychromatic Colorings of Some Plane Graphs

摘要: 一个平面图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).