Polychromatic Colorings of Plane Graphs
Polychromatic Colorings of Plane Graphs
复制标题
平面图的多色着色
DOI：
10.1145/1377676.1377734
复制
发表时间：
2008
影响因子：
0.8
通讯作者：
P. Zumstein
中科院分区：
文献类型：
--
作者：
N. Alon;R. Berke;K. Buchin;M. Buchin;P. Csorba;Saswata Shannigrahi;B. Speckmann;P. Zumstein
本文证明了任何平面图的顶点都可以被n（3g-5）/4 n（4）色着色，使得每种颜色都出现在每一个面上，其中每一个面至少与g个顶点相关联。这几乎是紧的，因为存在平面图，其中所有的面都关联到至少g个顶点，并且不允许这种类型的顶点着色超过3g（3g+1）/4g。我们进一步证明，确定一个平面图是否允许一个顶点着色k种颜色，其中所有的颜色出现在每个面上的问题是在k=2的情况下，
$\mathcal{NP}$
- 对于k= 3，4是完全的。我们完善这一结果多色3-着色限制到2-连通图，从一个规定的（可能是无限的）一组整数的面大小。因此，我们找到了这些整数集（面大小）的几乎完全的特征，对于这些整数集，相应的决策问题是不确定的，对于其他整数集，则是不确定的。
$\mathcal{NP}$
- 完成。
AbstractWe show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3g−5)/4⌋ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ⌊(3g+1)/4⌋ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in ℘ for k=2 and is
$\mathcal{NP}$
-complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in ℘, and for the others it is
$\mathcal{NP}$
-complete.