Conflict-Free Coloring Bounds on Open Neighborhoods

Abstract

In an undirected graph $G$, a conflict-free coloring with respect to open neighborhoods (denoted by CFON coloring) is an assignment of colors to the vertices such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for a CFON coloring of $G$ is the CFON chromatic number of $G$, denoted by $\chi_{ON}(G)$. The decision problem that asks whether $\chi_{ON}(G) \leq k$ is NP-complete. Structural as well as algorithmic aspects of this problem have been well studied. We obtain the following results for $\chi_{ON}(G)$:

All our bounds are a result of constructive algorithmic procedures.

Publication
Algorithmica, Volume 84, pages 2154-2185

Related