mercredi 12 juin 2024

Bruce Reed, distinguished Research Fellow, Taiwan, gives a présentation on 12 June 2024 at 2pm at INRIA in the Euler building, room E006.

TITLE : Peaceful and conflict free colourings

ABSTRACT: 

A {\it 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 {\it $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 {\it $p$-peaceful colouring} to be a colouring $f$ with no monochromatic edges in which
for every vertex $v$, $$|\{w \in N(v) : \exists u \in N(v)-\{w\} \text{ with } f(u)=f(w)\}| \le 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.