Peaceful Colourings

Abstract

We introduce peaceful colourings, a variant of $h$-conflict free colourings. We call a colouring with no monochromatic edges $p$-peaceful if for each vertex $v$, there are at most $p$ neighbours of $v$ coloured with a colour appearing on another neighbour of $v$. An $h$-conflict-free colouring of a graph is a (vertex)-colouring with no monochromatic edges so that for every vertex $v$, the number of neighbours of $v$ which are coloured with a colour appearing on no other neighbour of $v$ is at least the minimum of $h$ and the degree of $v$. If $G$ is $\hat{I}”$-regular then it has an $h$-conflict free colouring precisely if it has a $(\hat{I}”-h)$-peaceful colouring. We focus on the minimum $p_{\hat{I}}”$ of those $p$ for which every graph of maximum degree $\hat{I}”$ has a $p$-peaceful colouring with $\hat{I}”+1$ colours. We show that $p_{\hat{I}}”>(1-\frac{1}{e}-o(1))\hat{I}”$ and that for graphs of bounded codegree, $p_{\hat{I}}”\le (1-\frac{1}{e}+o(1))\hat{I}”$. We ask if the latter result can be improved by dropping the bound on the codegree. As a partial result, we show that $p_{\hat{I}}”\le \frac{8000}{8001}\hat{I}”$ for sufficiently large $\hat{I}”$.