The degeneracy conjecture for proper conflict-free list coloring
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.