论文标题
相对于社区的适当无冲突和独特的最大最大颜色
Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
论文作者
论文摘要
图形{\ em相对于open}（resp。，{\ em闭合}）{\ em neighboild}的{\ em无冲突的着色} {\ em neighboungriep}是顶点的着色，使得每个顶点都有一个颜色完全出现在其开放式（spect。同样，图形{\ em相对于open}的{\ em unique-maximum着色}（resp。，{\ em闭合}）{\ em邻域}是顶点的着色，使每个顶点的最大颜色出现在其开放式（spect。，封闭）中的最大颜色完全出现。在两个概念上都有大量文献，其中颜色不合适，即允许相邻的顶点具有相同的颜色。 在本文中，我们在适当的设置中启动了两种颜色的研究，其重点主要是平面图。我们为所有被考虑的颜色的平面图类别的颜色数量建立上限，并提供平面图的构造，从而获得相应的色数值相对较高的值。作为主要结果，我们证明，每个平面图都以最多的10种颜色的开放式邻域的形式承认适当的独特最大颜色，并给出了平面图的示例，需要至少$ 6 $颜色的颜色来进行这种颜色。我们还为外平面图建立了紧密的上限。最后，我们还为不当的颜色提供了几个新的界限。
A {\em conflict-free coloring} of a graph {\em with respect to open} (resp., {\em closed}) {\em neighborhood} is a coloring of vertices such that for every vertex there is a color appearing exactly once in its open (resp., closed) neighborhood. Similarly, a {\em unique-maximum coloring} of a graph {\em with respect to open} (resp., {\em closed}) {\em neighborhood} is a coloring of vertices such that for every vertex the maximum color appearing in its open (resp., closed) neighborhood appears exactly once. There is a vast amount of literature on both notions where the colorings need not be proper, i.e., adjacent vertices are allowed to have the same color. In this paper, we initiate a study of both colorings in the proper settings with the focus given mainly to planar graphs. We establish upper bounds for the number of colors in the class of planar graphs for all considered colorings and provide constructions of planar graphs attaining relatively high values of the corresponding chromatic numbers. As a main result, we prove that every planar graph admits a proper unique-maximum coloring with respect to open neighborhood with at most 10 colors, and give examples of planar graphs needing at least $6$ colors for such a coloring. We also establish tight upper bounds for outerplanar graphs. Finally, we provide several new bounds also for the improper setting of considered colorings.
