On variants of conflict-free-coloring for hypergraphs

详细信息    查看全文

• 作者：Zhen Cui^a ; Ze-Chun Hu^b ; ^{zchu@scu.edu.cn}
• 关键词：Conflict-free coloring ; Hypergraph ; One dimensional lattice
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：31 March 2017
• 年：2017
• 卷：220
• 期：Complete
• 页码：46-54
• 全文大小：427 K
• 卷排序：220

文摘

Conflict-free coloring is a kind of vertex coloring of hypergraphs requiring each hyperedge to have a color which appears only on one vertex. More generally, for a positive integer kk there are kk-conflict-free colorings (kk-CF-colorings for short) and kk-strong-conflict-free colorings (kk-SCF-colorings for short). Let HnHn be the hypergraph of which the vertex-set is Vn={1,2,…,n}Vn={1,2,…,n} and the hyperedge-set EnEn is the set of all (non-empty) subsets of VnVn consisting of consecutive elements of VnVn. Firstly, we study the kk-SCF-coloring of HnHn, give the exact kk-SCF-coloring chromatic number of HnHn for k=2,3k=2,3, and present upper and lower bounds of the kk-SCF-coloring chromatic number of HnHn for all kk. Secondly, we give the exact kk-CF-coloring chromatic number of HnHn for all kk.