论文标题
有限度图的封闭社区上的无冲突着色
Conflict-free coloring on closed neighborhoods of bounded degree graphs
论文作者
论文摘要
$χ_{cn}（g）$表示的封闭的邻域无冲突的$ g $的无冲突色数是为$ g $的顶点着色所需的最小颜色数量，因此对于每个顶点，都会出现一次颜色一次，而颜色恰好出现在其封闭的社区中。 Pach和Tardos [Combin。概率。计算。 2009年]表明，对于任何$ \ varepsilon> 0 $，其中$δ$是最高度。在[combin。概率。计算。 2014年，Glebov，Szabó和Tardos显示了图$ G $的存在，其中$χ_{cn}（g）=ω（\ log^2δ）$。在本文中，我们通过证明$χ_{Cn}（g）= O（\ log^2Δ）$来弥合两个边界之间的差距。
The closed neighborhood conflict-free chromatic number of a graph $G$, denoted by $χ_{CN}(G)$, is the minimum number of colors required to color the vertices of $G$ 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+\varepsilon} Δ)$, for any $\varepsilon > 0$, where $Δ$ is the maximum degree. In [Combin. Probab. Comput. 2014], Glebov, Szabó and Tardos showed existence of graphs $G$ with $χ_{CN}(G) = Ω(\log^2Δ)$. In this paper, we bridge the gap between the two bounds by showing that $χ_{CN}(G) = O(\log^2 Δ)$.
