Conflict-free coloring on closed neighborhoods of bounded degree graphs

preprint2020arXivOpen access

Abstract

The closed neighborhood conflict-free chromatic number of a graph GG, denoted by χCN(G)χ_{CN}(G), is the minimum number of colors required to color the vertices of GG such that for every vertex, there is a color that appears exactly once in its closed neighborhood. Pach and Tardos [Combin. Probab. Comput. 2009] showed that χCN(G)=O(log⁡2+εΔ)χ_{CN}(G) = O(\log^{2+\varepsilon} Δ), for any ε>0\varepsilon > 0, where ΔΔ is the maximum degree. In [Combin. Probab. Comput. 2014], Glebov, Szabó and Tardos showed existence of graphs GG with χCN(G)=Ω(log⁡2Δ)χ_{CN}(G) = Ω(\log^2Δ). In this paper, we bridge the gap between the two bounds by showing that χCN(G)=O(log⁡2Δ)χ_{CN}(G) = O(\log^2 Δ).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.