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-1e-o (1) ) and that for graphs of bounded codegree, p_ (1-1e+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_ 80008001 for sufficiently large.