arxiv: 2605.10776 · v1 · submitted 2026-05-11 · 🧮 math.CO · cs.DM

Recognition: 2 theorem links

· Lean Theorem

Computational and Combinatorial Results on Conflict-free Choosability

Rogers Mathew, Shiwali Gupta

Pith reviewed 2026-05-12 04:16 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords conflict-free coloringchoosabilitylist coloringK_{1,k}-free graphsneighborhood coloringchoice numberNP-hardnessgraph coloring

0 comments

The pith

Every K_{1,k}-free graph has CFCN* choice number O(k ln Δ), with NP-hardness for deciding if the choice number equals 1 or 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the conflict-free closed neighborhood choice number for any K_{1,k}-free graph is bounded above by a constant times k times the natural log of the maximum degree. This extends an earlier bound that held only for ordinary colorings, now allowing each vertex to draw its color from an arbitrary list of that many colors while still ensuring a partial coloring where every closed neighborhood contains exactly one occurrence of some color. The work further proves that deciding whether a graph has CFCN* or CFON* choice number exactly equal to k is NP-hard when k is 1 or 2.

Core claim

The combinatorial arguments previously used to bound the CFCN* chromatic number of K_{1,k}-free graphs extend directly to the list setting, so every such graph has CFCN* choice number O(k ln Δ). In addition, it is NP-hard to decide whether the CFCN* choice number or the CFON* choice number of an arbitrary graph equals k, for each fixed k in {1,2}.

What carries the argument

The CFCN* choice number: the smallest integer k such that, for any assignment of k-element lists to the vertices, a subset of vertices can be colored from their lists so that every vertex has a color appearing exactly once in its closed neighborhood.

If this is right

The O(k ln Δ) bound on the number of colors needed holds for the list version of CFCN* coloring.
Deciding whether the CFCN* choice number of a graph equals 1 is NP-hard.
Deciding whether the CFCN* choice number of a graph equals 2 is NP-hard.
The same NP-hardness holds for deciding whether the CFON* choice number equals 1 or 2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same direct transfer of arguments may apply to list versions of other neighborhood-based coloring parameters on K_{1,k}-free graphs.
The hardness for exact decision at k=1 and k=2 implies that no efficient algorithm exists to verify whether a given list assignment admits a valid conflict-free neighborhood coloring with those few colors.

Load-bearing premise

The combinatorial arguments that bounded the ordinary CFCN* chromatic number in K_{1,k}-free graphs apply unchanged once colors must be chosen from given lists.

What would settle it

A concrete K_{1,k}-free graph with maximum degree Δ together with an explicit list assignment of size C k ln Δ for which no valid partial coloring exists, where C is the hidden constant in the claimed bound.

Figures

Figures reproduced from arXiv: 2605.10776 by Rogers Mathew, Shiwali Gupta.

**Figure 1.** Figure 1: The graph G′ ϕ , where ϕ = (x1∨x2∨x3)∧(x1∨x2∨x5)∧(x1∨x3∨x5)∧(x3∨x4∨x5). ϕ is satisfiable by setting x1, x4 to be true. The black vertices will receive a color from their respective lists in any valid CFON∗ -coloring of the graph. Claim 23. The formula ϕ is a yes instance of the Positive Planar 1-in-3-SAT Problem if and only if G′ ϕ is 1-CFON∗ -choosable. Proof of claim. Suppose ϕ is a yes instance, that i… view at source ↗

**Figure 2.** Figure 2: The graph Gϕ with four clauses (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x5) ∧ (x1 ∨ x3 ∨ x5) ∧ (x3 ∨ x4 ∨ x5). ϕ is satisfiable by setting x1, x4 to be true. The black vertices will receive a color from their respective lists in any valid CFCN∗ -coloring of the graph. We observe that, under the coloring f, the variable gadget for each variable xi has exactly one vertex colored; either the vertex xi or the vertex vi . W… view at source ↗

**Figure 3.** Figure 3: The graph HG. For ℓ ∈ [4], 1 ≤ i < j ≤ 4, and z ∈ {a, b}, a dotted edge from vℓ to Gz ij indicates that vℓ is adjacent to every vertex in Gz ij . 12 [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

read the original abstract

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\k{e}bski and Przyby\l o [Journal of Graph Theory, 2022] showed that for any graph $G$ with maximum degree $\Delta$, the CFCN$^*$ chromatic number of its line graph is $O(\ln \Delta)$. This result was later extended to claw-free graphs by Bhyravarapu et al. [Journal of Graph Theory, 2025], who proved that every $K_{1,k}$-free graph $G$ admits a CFCN$^*$ coloring using $O(k\ln \Delta)$ 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(k\ln \Delta)$. 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the list-coloring version of the O(k ln Δ) CFCN* bound on K_{1,k}-free graphs plus NP-hardness for deciding if the choice number is exactly 1 or 2.

read the letter

The two things worth knowing are the O(k ln Δ) bound on CFCN* choice number for K_{1,k}-free graphs and the NP-hardness results for deciding whether the CFCN*/CFON* choice number equals 1 or 2. Both are direct extensions of earlier chromatic-number work and answer questions left open in Gupta and Mathew's SOFSEM paper. The list bound follows by swapping global color pools for per-vertex list sampling inside the same selection argument used for the non-list case; the stress-test indicates no new obstructions appear in the closed-neighborhood uniqueness condition, so the same asymptotic bound carries over. The hardness reductions are separate from the K_{1,k}-free setting and rely on standard gadget constructions for small k. What the paper does cleanly is supply concrete, usable bounds and settle the small-k decision problems without introducing extra parameters or fitted quantities. The combinatorial core stays close to the cited prior results, which keeps the claims grounded. The main soft spot is that the list adaptation is described at a high level in the abstract; if the full proof is only a routine replacement of color availability with list sampling, the technical lift is modest rather than deep. The hardness statements look independent and standard, so they should hold up under checking. This is a paper for people already working on conflict-free coloring and choosability variants. A reader outside that niche will find the scope narrow, but inside it the results are usable and the hardness answers are worth having. It deserves a serious referee because the claims are specific, the reductions are falsifiable, and the bound is stated in a form that can be verified against the earlier chromatic proofs.

Referee Report

0 major / 3 minor

Summary. The manuscript defines the CFCN* and CFON* choice numbers as list-coloring analogues of the corresponding conflict-free neighborhood chromatic numbers. It proves that every K_{1,k}-free graph has CFCN* choice number O(k ln Δ), extending the chromatic-number bound of Bhyravarapu et al. to arbitrary lists. It also establishes that deciding whether the CFCN* or CFON* choice number of an arbitrary graph equals k is NP-hard for k = 1 and k = 2, answering questions of Gupta and Mathew.

Significance. If the central claims hold, the work is significant for showing that the combinatorial selection arguments used for K_{1,k}-free graphs carry over to the list setting without increasing the asymptotic bound. This indicates robustness of the closed-neighborhood uniqueness condition under per-vertex list sampling. The NP-hardness results supply the first complexity lower bounds for these choice-number parameters and directly resolve the cited open questions.

minor comments (3)

Abstract: the two sentences defining the CFCN* choice number are nearly identical; a single consolidated definition would improve readability.
Introduction, paragraph 3: the citation 'Gupta and Mathew [SOFSEM, 2026]' lacks a full bibliographic entry; please supply the complete reference.
Section 4 (hardness section): the gadget for the k=2 CFON* reduction should explicitly verify that no auxiliary vertex creates an unintended unique color in an open neighborhood outside the intended reduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, as well as the recommendation for minor revision. The referee correctly identifies the extension of the O(k ln Δ) bound to the list setting for K_{1,k}-free graphs and the resolution of the NP-hardness questions for choice numbers 1 and 2.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core result generalizes the O(k ln Δ) CFCN* bound from Bhyravarapu et al. (2025) to the list-choice setting by adapting the existing combinatorial selection argument to per-vertex lists inside the same probabilistic/greedy framework; this extension is presented as a direct proof step rather than a redefinition or fit. The NP-hardness reductions for exact CFCN*/CFON* choice-number decision (k=1,2) are constructed via independent gadgets and do not rely on the bound or on any self-referential input. Self-citations (including to the authors' own SOFSEM 2026 paper for open questions) are non-load-bearing and serve only to contextualize the new hardness results. No equation or claim reduces by construction to a fitted parameter, renamed ansatz, or self-citation chain; the derivation is self-contained against the cited external literature.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or invented entities; the work relies on standard graph-theoretic definitions and asymptotic notation.

axioms (1)

standard math Standard definitions and closure properties of K_{1,k}-free graphs and maximum degree Δ
Invoked throughout the statement of the main bound.

pith-pipeline@v0.9.0 · 5733 in / 1217 out tokens · 46965 ms · 2026-05-12T04:16:36.645982+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
every K_{1,k}-free graph G has a CFCN* choice number of O(k ln Δ)
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
NP-hard to determine whether the CFCN*/CFON* choice number of a graph is equal to k, for k=1,2

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

Conflict-free coloring of graphs.SIAM Journal on Discrete Mathematics, 32(4):2675–2702, 2018

Zachary Abel, Victor Alvarez, Erik D Demaine, Sándor P Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, and Christian Scheffer. Conflict-free coloring of graphs.SIAM Journal on Discrete Mathematics, 32(4):2675–2702, 2018

work page 2018
[2]

Conflict-free colorings of shallow discs

Noga Alon and Shakhar Smorodinsky. Conflict-free colorings of shallow discs. In Proceedings of the twenty-second annual symposium on Computational geometry, pages 41–43, 2006

work page 2006
[3]

Extremal results on conflict-free coloring.Journal of Graph Theory, 109(3):259–268, 2025

Sriram Bhyravarapu, Shiwali Gupta, Subrahmanyam Kalyanasundaram, and Rogers Mathew. Extremal results on conflict-free coloring.Journal of Graph Theory, 109(3):259–268, 2025

work page 2025
[4]

A short note on conflict-free coloring on closed neighborhoods of bounded degree graphs.Journal of Graph Theory, 97(4):553–556, 2021

Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, and Rogers Mathew. A short note on conflict-free coloring on closed neighborhoods of bounded degree graphs.Journal of Graph Theory, 97(4):553–556, 2021

work page 2021
[5]

Conflict-free coloring on claw-free graphs and interval graphs

Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, and Rogers Mathew. Conflict-free coloring on claw-free graphs and interval graphs. In47th Interna- tional Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022

work page 2022
[6]

City University of New York, 2009

Panagiotis Cheilaris.Conflict-free coloring. City University of New York, 2009

work page 2009
[7]

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

Panagiotis Cheilaris, Shakhar Smorodinsky, and Marek Sulovsk` y. The potential to improve the choice: list conflict-free coloring for geometric hypergraphs. InPro- ceedings of the twenty-seventh annual symposium on Computational geometry, pages 424–432, 2011

work page 2011
[8]

Conflict-free chromatic number versus conflict- free chromatic index.Journal of Graph Theory, 99(3):349–358, 2022

Michał Dębski and Jakub Przybyło. Conflict-free chromatic number versus conflict- free chromatic index.Journal of Graph Theory, 99(3):349–358, 2022

work page 2022
[9]

Elbassioni and Nabil H

Khaled M. Elbassioni and Nabil H. Mustafa. Conflict-free colorings of rectangles ranges. In Bruno Durand and Wolfgang Thomas, editors,STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, volume 3884 ofLecture Notes in Computer Science, pages 254–263. Springer, 2006

work page 2006
[10]

Erdős and L

P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related questions.Infinite and finite sets, 10:609–627, 1975

work page 1975
[11]

Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks.SIAM Journal on Computing, 33(1):94–136, 2003

Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks.SIAM Journal on Computing, 33(1):94–136, 2003. 15

work page 2003
[12]

Conflict-free colouring of graphs

Roman Glebov, Tibor Szabó, and Gábor Tardos. Conflict-free colouring of graphs. Combinatorics, Probability and Computing, 23(3):434–448, 2014

work page 2014
[13]

Bounds and hardness results for conflict-free choosability

Shiwali Gupta and Rogers Mathew. Bounds and hardness results for conflict-free choosability. InInternational Conference on Current Trends in Theory and Practice of Computer Science, pages 461–474. Springer, 2026

work page 2026
[14]

On conflict-free coloring of points and simple regions in the plane

Sariel Har-Peled and Shakhar Smorodinsky. On conflict-free coloring of points and simple regions in the plane. InProceedings of the nineteenth annual symposium on Computational geometry, pages 114–123, 2003

work page 2003
[15]

Pliable index coding via conflict-free colorings of hypergraphs.IEEE Trans

Prasad Krishnan, Rogers Mathew, and Subrahmanyam Kalyanasundaram. Pliable index coding via conflict-free colorings of hypergraphs.IEEE Trans. Inf. Theory, 70(6):3903–3921, 2024

work page 2024
[16]

Conflict-freecoloringofunitdisks.Discrete Applied Mathematics, 157(7):1521–1532, 2009

NissanLev-TovandDavidPeleg. Conflict-freecoloringofunitdisks.Discrete Applied Mathematics, 157(7):1521–1532, 2009

work page 2009
[17]

Michael Molloy and Bruce A. Reed. Colouring graphs when the number of colours is almost the maximum degree.J. Comb. Theory, Ser. B, 109:134–195, 2014

work page 2014
[18]

Minimum-weight triangulation is np-hard.Jour- nal of the ACM (JACM), 55(2):1–29, 2008

Wolfgang Mulzer and Günter Rote. Minimum-weight triangulation is np-hard.Jour- nal of the ACM (JACM), 55(2):1–29, 2008

work page 2008
[19]

Conflict-free colourings of graphs and hypergraphs

János Pach and Gábor Tardos. Conflict-free colourings of graphs and hypergraphs. Combinatorics, Probability and Computing, 18(5):819–834, 2009

work page 2009
[20]

Conflict-free colorings

János Pach and Géza Tóth. Conflict-free colorings. InDiscrete and Computational Geometry: The Goodman-Pollack Festschrift, pages 665–671. Springer, 2003

work page 2003
[21]

Springer Berlin Heidelberg, Berlin, Heidelberg, 2013

Shakhar Smorodinsky.Conflict-Free Coloring and its Applications, pages 331–389. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013

work page 2013
[22]

List conflict-free coloring of planar graphs.Acta Mathe- maticae Applicatae Sinica, English Series, pages 1–10, 2025

Ya-li Wu and Xin Zhang. List conflict-free coloring of planar graphs.Acta Mathe- maticae Applicatae Sinica, English Series, pages 1–10, 2025. 16

work page 2025