A (partial) conflict-free coloring of a hypergraph \(\mathcal {H}\) is an assignment of colors to (a subset of) the vertex set of \(\mathcal {H}\) such that every hyperedge in \(\mathcal {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 \(\mathcal {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 \(L_v\) such that v is allowed to be colored only from \(L_v\) . It was shown by Pach and Tardos [Combinatorics, Probability and Computing, 2009] that for any constant \(\epsilon > 0\) , the closed-neighborhood conflict-free chromatic number of a graph G is at most \(O(\ln ^{2 + \epsilon }\varDelta )\) , where \(\varDelta \) represents the maximum degree of G. Later, Glebov, Szabó, and Tardos [Combinatorics, Probability and Computing, 2014] showed that there exist graphs G that require \(\varOmega (\ln ^2\varDelta )\) colors for a closed neighborhood conflict-free coloring. Bhyravarapu, Kalyanasundaram, and Mathew [Journal of Graph Theory, 2021] bridged the gap between the upper and the lower bound. They showed that the closed-neighborhood conflict-free chromatic number of any graph G is at most \(O(\ln ^2 \varDelta )\) . In this paper, we extend the \(O(\ln ^2 \varDelta )\) 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bounds and Hardness Results for Conflict-Free Choosability

  • Shiwali Gupta,
  • Rogers Mathew

摘要

A (partial) conflict-free coloring of a hypergraph \(\mathcal {H}\) is an assignment of colors to (a subset of) the vertex set of \(\mathcal {H}\) such that every hyperedge in \(\mathcal {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 \(\mathcal {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 \(L_v\) such that v is allowed to be colored only from \(L_v\) . It was shown by Pach and Tardos [Combinatorics, Probability and Computing, 2009] that for any constant \(\epsilon > 0\) , the closed-neighborhood conflict-free chromatic number of a graph G is at most \(O(\ln ^{2 + \epsilon }\varDelta )\) , where \(\varDelta \) represents the maximum degree of G. Later, Glebov, Szabó, and Tardos [Combinatorics, Probability and Computing, 2014] showed that there exist graphs G that require \(\varOmega (\ln ^2\varDelta )\) colors for a closed neighborhood conflict-free coloring. Bhyravarapu, Kalyanasundaram, and Mathew [Journal of Graph Theory, 2021] bridged the gap between the upper and the lower bound. They showed that the closed-neighborhood conflict-free chromatic number of any graph G is at most \(O(\ln ^2 \varDelta )\) . In this paper, we extend the \(O(\ln ^2 \varDelta )\) 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.