A Short Note on Open-Neighborhood Conflict-Free Colorings of Graphs
Fei Huang, Shanshan Guo, Jinjiang Yuan · SIAM Journal on Discrete Mathematics · 2020
A graph is said to be open-neighborhood conflict-free $k$-colorable if there exists an assignment of $k$ different colors to some of the vertices such that, for every vertex $v$, there is a color that is assigned to exactly one vertex among the neighbors of $v$. The open-neighborhood conflict-free chromatic number $\chi _O(G)$ is the smallest $k$ for which $G$ is open-neighborhood conflict-free $k$-colorable. Z. Abel et al., [ SIAM J. Discrete Math. 32 (2018), pp. 2675--2702] showed that $\chi _O(G)\leq 8$ for every planar graph $G$ and posed two open problems to ask whether $\chi _O(G)\leq 4$ for every planar graph $G$ and whether $\chi _O(G)\leq 3$ for every outerplanar graph $G$. We present in this paper positive answers for the above two open problems by establishing a stronger result which states that, for every integer $k\ge 2$, every minor-$k$-colorable graph is open-neighborhood conflict-free $k$-colorable, where a graph $G$ is said to be minor-$k$-colorable if every minor of $G$ is $k$-colorable.