The degeneracy conjecture for proper conflict-free list coloring

About 1 year old · traced to

A graph is dd-degenerate if every nonempty subgraph has a vertex of degree at most dd. A list assignment LL assigns a list of colors L(v)L(v) to each vertex vv; the graph is proper conflict-free (degree+d)({\rm degree}+d)-choosable if, for every such assignment satisfying ∣L(v)∣≥deg⁡G(v)+d|L(v)|\geq \deg_G(v)+d for all vertices vv, one can choose a color from each list to obtain a proper conflict-free coloring.

Degeneracy conjecture for proper conflict-free list coloring. If GG is a dd-degenerate graph for some positive integer dd, then GG is proper conflict-free (degree+d)({\rm degree}+d)-choosable.

The statement is motivated by the proved tree case, where the bound is (degree+1)({\rm degree}+1), and by constructions showing that the corresponding bounds cannot generally be lowered. The supplied text gives no evidence that this conjecture has been resolved.

References

Primary source

Masaki Kashima, Riste Škrekovski and Rongxing Xu, “Remarks on proper conflict-free degree-choosability of graphs with prescribed degeneracy”, arXiv:2509.12560 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.