2024/09/19 by Shiwali Gupta, Gupta, Shiwali, Rogers Mathew +1
Decision Sciences · #05C15 #05C35 #05D40 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.2409.12672
openalex publication_date 2024/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A '(partial) conflict-free coloring' of a hypergraph H is an assignment of colors to (a subset of) the vertex set of H such that every hyperedge in H has a vertex whose color is distinct from every other vertex in that hyperedge. The minimum number of colors required for such a coloring is known as the '(partial) conflict-free chromatic number' of H. It is easy to see that the conflict-free chromatic number of a hypergraph is at most its partial conflict-free chromatic number plus one. Conflict-free coloring has also been studied on the open/closed neighborhood hypergraphs of a given graph under the name open/closed neighborhood conflict-free coloring. In this paper, we study partial and full list variants of conflict-free coloring where, for every vertex v, we are given a list of admissible colors Lv such that v is allowed to be colored only from Lv. Bhyravarapu, Kalyanasundaram, and Mathew [Journal of Graph Theory, 2021] showed that the closed-neighborhood conflict-free chromatic number of any graph G with maximum degree Δ is at most O(ln2 Δ). In this paper, we extend the O(ln2 Δ) upper bound to the partial list variant of the closed-neighborhood conflict-free chromatic number. Further, we establish computational complexity results concerning the list open/closed-neighborhood conflict-free chromatic numbers.