The degeneracy conjecture for proper conflict-free list coloring

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)degG(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.

Sources & referencesView supporting material

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.