Search

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 χ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 χ O(G) ≤ 8 for every planar graph G and posed two open problems to ask whether χO(G) \leq 4 for every planar graph G and whether χO(G) ≤ 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 ≥ 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. [ABSTRACT FROM AUTHOR]