Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs

Abstract

A Conflict-Free Open Neighborhood coloring, abbreviated CFON* coloring, of a graph $G = (V,E)$ using $k$ colors is an assignment of colors from a set of $k$ colors to a subset of vertices of $V(G)$ such that every vertex sees some color exactly once in its open neighborhood. The minimum $k$ for which $G$ has a CFON* coloring using $k$ colors is called the _CFON* chromatic number_ of $G$, denoted by $\chi_{ON}^*(G)$. The analogous notion for closed neighborhood is called CFCN* coloring and the analogous parameter is denoted by $\chi_{CN}^*(G)$. The problem of deciding whether a given graph admits a CFON* (or CFCN*) coloring that uses $k$ colors is NP-complete. Below, we describe briefly the main results of this paper.

Publication
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science - MFCS 2022, Vienna, Austria

Related