Search Results

The conflict-free closed neighborhood (CFCN^*) chromatic number of a graph G = (V,E) is the smallest positive integer k for which there exists a coloring of a subset of vertices using k colors such that, for every vertex in V, there exists a color that appears exactly once in its closed neighborhood. The conflict-free open neighborhood (CFON^*) chromatic number is defined analogously. In this paper, we study "list variants" of the above-mentioned coloring parameters. The conflict-free closed neighborhood (CFCN^*) choice number of a graph G = (V,E) is the smallest positive integer k such that for every assignment of lists of size k to its vertices, there exists a coloring of a subset of vertices, say V', in which (i) every vertex in V' receives a color from its list, and (ii) for every vertex in V there exists some color that appears exactly once in its closed neighborhood. The conflict-free open neighborhood (CFON^*) choice number is defined analogously. Dębski and Przybyło [Journal of Graph Theory, 2022] showed that for any graph G with maximum degree Δ, the CFCN^* chromatic number of its line graph is O(ln Δ). This result was later extended to claw-free graphs by Bhyravarapu et al. [Journal of Graph Theory, 2023], who proved that every K_{1,k}-free graph G admits a CFCN^* coloring using O(kln Δ) colors. In this paper, we generalize this result to the list setting and show that every K_{1,k}-free graph G has a CFCN^* choice number of O(kln Δ). Further, we answer some questions concerning the hardness of computing CFCN^*/CFON^* choice numbers posed by Gupta and Mathew [SOFSEM, 2026]; in particular, we show that it is NP-hard to determine whether the CFCN^*/CFON^* choice number a graph is equal to k, for k = 1,2.