On conflict-free proper colourings of graphs without small degree vertices

Abstract

A proper vertex colouring of a graph $G$ is referred to as conflict-free if in the neighbourhood of every vertex some colour appears exactly once, while it is called $h$-conflict-free if there are at least $h$ such colours for each vertex of $G$. The least numbers of colours in such colourings of $G$ are denoted ${\chi }_{\mathrm{pcf}}(G)$ and ${\chi }_{\mathrm{pcf}}^h(G)$, respectively. It is known that ${\chi }_{\mathrm{pcf}}^h(G)$ can be as large as $(h+1)(\Delta +1)\approx {\Delta }^2$ for graphs with maximum degree $\Delta$ and $h$ very close to $\Delta$. We provide several new upper bounds for these parameters for graphs with minimum degrees $\delta$ large enough and $h$ detached from $\delta$. In particular we show that ${\chi }_{\mathrm{pcf}}^h(G)\le (1+o(1))\Delta$ if $\delta \gg \ln \Delta$ and $h\ll \delta$, and that ${\chi }_{\mathrm{pcf}}(G)\le \Delta +O(\ln \Delta )$ for regular graphs. These specifically refer to the conjecture of Caro, Petruševski and Škrekovski that ${\chi }_{\mathrm{pcf}}(G)\le \Delta +1$ for every connected graph $G$ of maximum degree $\Delta \ge 3$, towards which they proved that ${\chi }_{\mathrm{pcf}}(G)\le \lfloor \frac{5\Delta }{2}\rfloor$ if $\Delta \ge 1$.

8 pages