Peaceful Colourings

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 Δ-regular then it has an h-conflict free colouring precisely if it has a (Δ-h)-peaceful colouring. We focus on the minimum p_Δ of those p for which every graph of maximum degree Δ has a p-peaceful colouring with Δ+1 colours. We show that p_Δ > (1-1/e-o(1))Δ and that for graphs of bounded codegree, p_Δ ≤ (1-1/e+o(1))Δ. We ask if the latter result can be improved by dropping the bound on the codegree. As a partial result, we show that p_Δ ≤ 8000/8001Δ for sufficiently large Δ.