Asymptotically Optimal Proper Conflict-Free Colouring

Abstract

A proper conflict-free colouring of a graph is a colouring of the vertices such that any two adjacent vertices receive different colours, and for every non-isolated vertex $v$, some colour appears exactly once on the neighbourhood of $v$. Caro, PetruÅ¡evski and Å krekovski conjectured that every connected graph with maximum degree $\hat{I}”\ge 3$ has a proper conflict-free colouring with at most $\hat{I}”+1$ colours. This conjecture holds for $\hat{I}”=3$ and remains open for $\hat{I}”\ge 4$. In this paper we prove that this conjecture holds asymptotically; namely, every graph with maximum degree $\hat{I}”$ has a proper conflict-free colouring with $(1+o(1))\hat{I}”$ colours.