PIMS-UVic Discrete Math Seminar: Bruce Reed

A proper conflict-free colouring of a graph is a (vertex-)colouring with no monochromatic edges such that for every nonisolated vertex v, the neighbourhood N(v) contains a vertex w coloured with a colour not appearing on N(v)-{w}. For a real number h, a colouring of a graph with no monochromatic edges is h-conflict-free if for every vertex v, N(v) contains at least min{deg(v), h} vertices coloured with a colour used only once in N(v). For a real number p, we define a p-peaceful colouring to be a colouring f with no monochromatic edges in which for every vertex v,

|{w in N(v) : there exists u in N(v)-{w} with f(u)=f(w)}| ≤ p.

We note that for a d-regular graph, a colouring is an h-conflict-free proper colouring precisely if it is a (d-h)-peaceful colouring. In contrast, if G is an irregular graph of maximum degree Delta then while a p-peaceful colouring and a (\Delta-p)-conflict-free colouring impose the same condition on maximum degree vertices, the peaceful colouring imposes weaker conditions on low degree vertices. We present some results on these three types of colourings. These are joint work with Chun-hung Liu.