Caro–Petruševski–Škrekovski conjecture on proper conflict-free chromatic number

About 4 years old · traced to

Let GG be a connected simple finite graph with maximum degree e=3e=3. 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; cPCF(G)c_{\rm PCF}(G) denotes the minimum number of colors in such a coloring.

Caro–Petruševski–Škrekovski conjecture. The proper conflict-free chromatic number satisfies

χPCF(G)≤Δ+1.\chi_{\rm PCF}(G) \leq \Delta+1.

Caro, Petruševski, and Škrekovski proved the general upper bound χPCF(G)≤⌊5Δ(G)/2⌋\chi_{\rm PCF}(G)\leq\lfloor 5\Delta(G)/2\rfloor; the conjecture would improve this bound for connected graphs of maximum degree at least 33.

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

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.