Exposé de Bruce Reed

mercredi 12 juin 2024
Bruce Reed, distinguished Research Fellow, Taiwan, will give a présentation on June 12th, 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.