The degeneracy conjecture for proper conflict-free list coloring
A graph is -degenerate if every nonempty subgraph has a vertex of degree at most . A list assignment assigns a list of colors to each vertex ; the graph is proper conflict-free -choosable if, for every such assignment satisfying for all vertices , one can choose a color from each list to obtain a proper conflict-free coloring.
Degeneracy conjecture for proper conflict-free list coloring. If is a -degenerate graph for some positive integer , then is proper conflict-free -choosable.
The statement is motivated by the proved tree case, where the bound is , 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
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.