pith. sign in

arxiv: 2409.12672 · v4 · pith:4IJPSNVOnew · submitted 2024-09-19 · 🧮 math.CO · cs.DM

Bounds and Hardness Results for Conflict-free Choosability

Shiwali Gupta , Rogers Mathew This is my paper

Pith reviewed 2026-05-23 20:30 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords conflict-free coloringlist coloringpartial list coloringchoosabilityneighborhood hypergraphcomputational complexity
0
0 comments X

The pith

The partial list closed-neighborhood conflict-free chromatic number is O(ln² Δ) for any graph with maximum degree Δ.

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

The paper extends the O(ln² Δ) upper bound on closed-neighborhood conflict-free chromatic numbers to the partial list variant. This means that even when each vertex must choose its color from a given list and only some vertices are colored, the number of colors needed remains bounded by O(ln² Δ). The authors also establish computational complexity results for the list versions of open and closed neighborhood conflict-free chromatic numbers. A sympathetic reader would care because this shows the bound is robust to list restrictions, which are common in practical coloring problems with constraints.

Core claim

We prove that any graph G with maximum degree Δ has partial list closed-neighborhood conflict-free chromatic number O(ln² Δ). This extends the result of Bhyravarapu et al. for the non-list case. We further provide hardness results for computing the list open-neighborhood and closed-neighborhood conflict-free chromatic numbers.

What carries the argument

Partial list coloring of the closed-neighborhood hypergraph, where a subset of vertices receive colors from their lists so that every hyperedge has a vertex with a unique color.

If this is right

  • The O(ln² Δ) bound holds in the more general list setting.
  • Computational hardness applies to determining the list conflict-free numbers for neighborhood hypergraphs.
  • The general relation between partial and full conflict-free chromatic numbers carries over to the list case.

Where Pith is reading between the lines

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

  • Similar logarithmic bounds may apply to other variants of list hypergraph coloring.
  • This could simplify the design of conflict-free assignments in constrained systems like sensor networks.
  • Extensions to open neighborhoods in the partial list setting remain open for similar bounds.

Load-bearing premise

The closed-neighborhood hypergraph of any graph with maximum degree Δ admits a partial list conflict-free coloring with O(ln² Δ) colors.

What would settle it

A graph of maximum degree Δ for which the partial list closed-neighborhood conflict-free chromatic number grows faster than any constant times ln² Δ.

read the original abstract

A '(partial) conflict-free coloring' of a hypergraph $\mathcal{H}$ is an assignment of colors to (a subset of) the vertex set of $\mathcal{H}$ such that every hyperedge in $\mathcal{H}$ has a vertex whose color is distinct from every other vertex in that hyperedge. The minimum number of colors required for such a coloring is known as the '(partial) conflict-free chromatic number' of $\mathcal{H}$. It is easy to see that the conflict-free chromatic number of a hypergraph is at most its partial conflict-free chromatic number plus one. Conflict-free coloring has also been studied on the open/closed neighborhood hypergraphs of a given graph under the name open/closed neighborhood conflict-free coloring. In this paper, we study partial and full list variants of conflict-free coloring where, for every vertex $v$, we are given a list of admissible colors $L_v$ such that $v$ is allowed to be colored only from $L_v$. Bhyravarapu, Kalyanasundaram, and Mathew [Journal of Graph Theory, 2021] showed that the closed-neighborhood conflict-free chromatic number of any graph $G$ with maximum degree $\Delta$ is at most $O(\ln^2 \Delta)$. In this paper, we extend the $O(\ln^2 \Delta)$ upper bound to the partial list variant of the closed-neighborhood conflict-free chromatic number. Further, we establish computational complexity results concerning the list open/closed-neighborhood conflict-free chromatic numbers.

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.

Referee Report

0 major / 3 minor

Summary. The paper defines partial and full list variants of conflict-free coloring on hypergraphs (including open/closed neighborhood hypergraphs induced by graphs). It extends the O(ln² Δ) upper bound of Bhyravarapu et al. (JGT 2021) on closed-neighborhood conflict-free chromatic number to the partial-list setting, and establishes NP-hardness and other complexity results for the list open- and closed-neighborhood variants.

Significance. The extension demonstrates that the known logarithmic bound is robust under list constraints via an explicit adaptation of the non-list probabilistic/greedy argument; this is a non-trivial strengthening for choosability questions. The complexity results supply concrete hardness statements that complement the upper-bound work. The manuscript supplies the adapted proof directly rather than reducing to a prior result.

minor comments (3)
  1. [§2] §2 (Definitions): the distinction between 'partial' and 'full' list conflict-free coloring is introduced but the subsequent complexity statements in §4 would benefit from an explicit sentence clarifying which variant each hardness result applies to.
  2. [§3] The proof of the O(ln² Δ) list bound (presumably in §3) adapts the non-list argument; a short remark on whether the list-size assumption is exactly the same as the non-list case or requires an extra logarithmic factor would improve readability.
  3. [Table 1] Table 1 (complexity summary): the rows for open- vs. closed-neighborhood list variants should include a column or footnote indicating the precise list-size regime under which hardness holds.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

Minor self-citation to overlapping-author prior work; extension supplies independent adaptation

full rationale

The manuscript cites Bhyravarapu, Kalyanasundaram, and Mathew (2021) for the O(ln² Δ) bound on the non-list closed-neighborhood conflict-free chromatic number and states that it extends this bound to the partial list variant. The abstract and skeptic summary indicate an explicit proof adaptation is supplied that respects per-vertex lists, introducing no new fitted parameters or definitional reductions. The self-citation is therefore present but not load-bearing for the new claim, which remains self-contained via the described adaptation. No equations, ansatzes, or uniqueness theorems reduce the extension to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, ad-hoc axioms, or invented entities; the work relies on standard graph-theoretic definitions of neighborhood hypergraphs and list coloring.

axioms (1)
  • standard math The closed-neighborhood hypergraph of any graph is a valid hypergraph for conflict-free coloring definitions.
    Invoked implicitly when the bound is stated for closed-neighborhood conflict-free chromatic number.

pith-pipeline@v0.9.0 · 5805 in / 1136 out tokens · 19070 ms · 2026-05-23T20:30:02.498219+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Asymptotically Tight Bound for the Conflict-Free Chromatic Index

    math.CO 2026-04 accept novelty 8.0

    The conflict-free chromatic index is at most (1+o(1)) log₂ Δ for any graph and this bound is tight.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · cited by 1 Pith paper

  1. [1]

    Abel, Victor

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

    work page 2018

  2. [2]

    Conflict-free colori ngs of shallow discs

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

    work page 2006

  3. [3]

    Extremal results on conflict-free coloring

    Sriram Bhyravarapu, Shiwali Gupta, Subrahmanyam Kalyan asundaram, and Rogers Mathew. Extremal results on conflict-free coloring. CoRR, abs/2305.02570, 2023

    work page arXiv 2023

  4. [4]

    Conflict-free coloring on open neighborhoods of claw-free graphs

    Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, and Rogers Mathew. Conflict-free coloring on open neighborhoods of claw-free graphs. arXiv preprint arXiv:2112.12173 , 2021

    work page arXiv 2021

  5. [5]

    A short note on conflict-free coloring on closed neighborhoods of bo unded degree graphs

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

    work page 2021

  6. [6]

    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. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) . Schloss Dagstuhl-Leibniz- Zentrum für Informatik, 2022

    work page 2022

  7. [7]

    Bodlaender, Sudeshna Kolay, and Astrid Pieterse

    Hans L. Bodlaender, Sudeshna Kolay, and Astrid Pieterse. Parameterized complexity of conflict-free graph coloring. SIAM J. Discret. Math. , 35(3):2003–2038, 2021

    work page 2003

  8. [8]

    Conflict-free coloring

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

    work page 2009

  9. [9]

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

    Panagiotis Cheilaris, Shakhar Smorodinsky, and Marek S ulovsk` y. The potential to improve the choice: list conflict-free coloring for geometric hyper graphs. In Proceedings of the twenty- seventh annual symposium on Computational geometry , pages 424–432, 2011

    work page 2011

  10. [10]

    Conflict-free chroma tic number versus conflict-free chromatic index

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

    work page 2022

  11. [11]

    Elbassioni and Nabil H

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

    work page 2006

  12. [12]

    Erdős and L

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

    work page 1975

  13. [13]

    Conflict-free colorings of simple geometric regions with applications to frequency as signment in cellular networks

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

    work page 2004

  14. [14]

    Conflict-f ree colouring of graphs

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

    work page 2014

  15. [15]

    A hajós-like theorem for list colorin g

    Sylvain Gravier. A hajós-like theorem for list colorin g. Discrete Mathematics, 152(1-3):299– 302, 1996

    work page 1996

  16. [16]

    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. In Proceedings of the nineteenth annual symposium on Computat ional geometry, pages 114–123, 2003

    work page 2003

  17. [17]

    A short note on open-neighborhood conflict- free colorings of graphs

    Fei Huang, Shanshan Guo, and Jinjiang Yuan. A short note on open-neighborhood conflict- free colorings of graphs. SIAM Journal on Discrete Mathematics , 34(3):2009–2015, 2020

    work page 2009

  18. [18]

    Pliable index coding via conflict-free colorings of hypergraphs

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

    work page 2024

  19. [19]

    Conflict-free coloring of unit disks

    Nissan Lev-Tov and David Peleg. Conflict-free coloring of unit disks. Discrete Applied Mathematics, 157(7):1521–1532, 2009

    work page 2009

  20. [20]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge Univ Pr, 2005

    work page 2005

  21. [21]

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

    work page 2014

  22. [22]

    Conflict-free colourings o f graphs and hypergraphs

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

    work page 2009

  23. [23]

    Conflict-free colourings o f graphs and hypergraphs

    Janos Pach and Gábor Tardos. Conflict-free colourings o f graphs and hypergraphs. Com- binatorics, Probability and Computing , 18(5):819–834, 2009

    work page 2009

  24. [24]

    Conflict-free colorings

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

    work page 2003

  25. [25]

    Conflict-Free Coloring and its Applications , pages 331–389

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

    work page 2013