2026-07-22T16:11:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26186 2026-07-02T07:14:09Z ddc:004 open_access

Computational and Combinatorial Results on Conflict-Free Choosability Gupta, Shiwali Mathew, Rogers conflict-free coloring list conflict-free coloring choice number claw number computational complexity hardness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shiwali Gupta and Rogers Mathew 2026 Is Part Of LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WG.2026.20 urn:nbn:de:0030-drops-261868 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode