Graph unique-maximum and conflict-free colorings
Graph unique-maximum and conflict-free colorings
复制标题
DOI：
10.1016/j.jda.2011.03.005
复制
发表时间：
2009-12
期刊：
影响因子：
13.3
通讯作者：
Panagiotis Cheilaris;G. Tóth
中科院分区：
文献类型：
--
作者：
Panagiotis Cheilaris;G. Tóth
研究了图的两类顶点着色：唯一极大着色和无冲突着色之间的关系。在唯一最大着色中，颜色是有序的，并且在图的每条路径中，最大颜色只出现一次。在无冲突着色中，在图的每条路径上都有一种颜色只出现一次。我们还研究了无冲突着色的计算复杂性方面，并证明了一个完整的结果。最后，我们改进了格子图的这些色数的下界。
We investigate the relationship between two kinds of vertex colorings of graphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every path of the graph the maximum color appears only once. In a conflict-free coloring, in every path of the graph there is a color that appears only once. We also study computational complexity aspects of conflict-free colorings and prove a completeness result. Finally, we improve lower bounds for those chromatic numbers of the grid graph.