Caro–Petruševski–Škrekovski conjecture on proper conflict-free chromatic number
Let be a connected simple finite graph with maximum degree . A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a color appearing exactly once in its open neighborhood; denotes the minimum number of colors in such a coloring.
Caro–Petruševski–Škrekovski conjecture. The proper conflict-free chromatic number satisfies
Caro, Petruševski, and Škrekovski proved the general upper bound ; the conjecture would improve this bound for connected graphs of maximum degree at least .
References
Primary source
Yuting Wang and Xin Zhang, “Proper conflict-free choosability of planar graphs”, arXiv:2512.22805 (2025).
Additional references
7 papers in this index state this conjecture (2022–2025). The statement above is taken from the most recent of them; the others are arXiv:2509.12560, arXiv:2508.20521, arXiv:2401.02155, arXiv:2306.01341, arXiv:2302.06125, arXiv:2211.02818.
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.