On variants of conflict-free-coloring for hypergraphs

2011/07/01 by Zhen Cui, Cui, Zhen, Ze-Chun Hu +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Probability (math.PR) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1107.0138

openalex publication_date 2011/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 k there are k-conflict-free colorings (k-CF-colorings for short) and k-strong-conflict-free colorings (k-SCF-colorings for short). %for some positive integer k. Let H_n be the hypergraph of which the vertex-set is V_n=\1,2,…,n\ and the hyperedge-set \calE_n is the set of all (non-empty) subsets of V_n consisting of consecutive elements of V_n. Firstly, we study the k-SCF-coloring of H_n, give the exact k-SCF-coloring chromatic number of H_n for k=2,3, and present upper and lower bounds of the k-SCF-coloring chromatic number of H_n for all k. Secondly, we give the exact k-CF-coloring chromatic number of H_n for all k.

Cited by

• Strong Conflict-Free Coloring of Intervals

Related

• Bounds and Hardness Results for Conflict-free Choosability
• Conflict-Free Coloring and its Applications
• Conflict-free coloring with respect to a subset of intervals
• Unique-maximum and conflict-free colorings for hypergraphs and tree\n graphs
• Perfect Resolution of Strong Conflict-Free Colouring of Interval Hypergraphs