New bounds for proper $h$-conflict-free colourings

Abstract

A proper $k$-colouring of a graph $G$ is called $h$-conflict-free if every vertex $v$ has at least $\min \{h,\mathrm{deg}(v)\}$ colours appearing exactly once in its neighbourhood. Let ${\chi }_{\mathrm{pcf}}^h(G)$ denote the minimum $k$ such that such a colouring exists. We show that for every fixed $h\ge 1$, every graph $G$ of maximum degree $\Delta$ satisfies ${\chi }_{\mathrm{pcf}}^h(G)\le h\Delta +\mathcal{O}(\log \Delta )$. This expands on the work of Cho et al., and improves a recent result of Liu and Reed in the case $h=1$. We conjecture that for every $h\ge 1$ and every graph $G$ of maximum degree $\Delta$ sufficiently large, the bound ${\chi }_{\mathrm{pcf}}^h(G)\le h\Delta +1$ should hold, which would be tight. When the minimum degree $\delta$ of $G$ is sufficiently large, namely $\delta \ge \max \{100h,2000\log \Delta \}$, we show that this upper bound can be further reduced to ${\chi }_{\mathrm{pcf}}^h(G)\le \Delta +\mathcal{O}(\sqrt{h\Delta })$. This improves a recent bound from Kamyczura and Przybyło when $\delta \le \sqrt{h\Delta }$.

arXiv commentPublished version: minor correction in the proof of Lemma 25