论文标题
在开放社区上无星形图的无冲突着色
Conflict-Free Coloring of Star-Free Graphs on Open Neighborhoods
论文作者
论文摘要
鉴于图形，开放式邻域（CFON）上的无冲突着色问题要求为图的顶点着色，以便所有顶点在其开放式邻域中具有独特的彩色顶点。这种着色所需的最少数量的颜色称为无冲突的色数，并表示$χ_{on}（g）$。在本说明中，我们在$ s_k $ - free图上研究了此问题，其中$ s_k $是$ k+1 $ vertices的星。当$ g $是$ s_k $ -free时，我们表明$χ_{on}（g）= o（k \ cdot \ log^{2+ε}δ）$，对于任何$ε> 0 $，其中$Δ$表示$ g $的最大程度。此外，我们显示了需要$ω（\logδ）$颜色的无爪（$ s_3 $ - free）图。
Given a graph, the conflict-free coloring problem on open neighborhoods (CFON) asks to color the vertices of the graph so that all the vertices have a uniquely colored vertex in its open neighborhood. The smallest number of colors required for such a coloring is called the conflict-free chromatic number and denoted $χ_{ON}(G)$. In this note, we study this problem on $S_k$-free graphs where $S_k$ is a star on $k+1$ vertices. When $G$ is $S_k$-free, we show that $χ_{ON}(G) = O(k\cdot \log^{2+ε}Δ)$, for any $ε> 0$, where $Δ$ denotes the maximum degree of $G$. Further, we show existence of claw-free ($S_3$-free) graphs that require $Ω(\log Δ)$ colors.
