Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs
Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs
复制标题
DOI：
10.1137/120880471
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
Panagiotis Cheilaris;Balázs Keszegh;Dömötör Pálvölgyi
中科院分区：
文献类型：
--
作者：
Panagiotis Cheilaris;Balázs Keszegh;Dömötör Pálvölgyi
我们研究超图的两种顶点着色之间的关系：唯一最大着色和无冲突着色。在唯一最大着色中，颜色是有序的，并且在超图的每个超边中，该超边中的最大颜色仅出现在超边的一个顶点上。在无冲突着色中，在超图的每个超边中，存在一种颜色，它仅出现在超边的一个顶点上。我们定义了相应的唯一最大色数和无冲突色数，并研究它们在任意超图中的关系。然后，我们专注于由树图中的简单路径诱导出的超图。
We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color in the hyperedge occurs in only one vertex of the hyperedge. In a conflict-free coloring, in every hyperedge of the hypergraph there exists a color in the hyperedge that occurs in only one vertex of the hyperedge. We define corresponding unique-maximum and conflict-free chromatic numbers and investigate their relationship in arbitrary hypergraphs. Then, we concentrate on hypergraphs that are induced by simple paths in tree graphs.