14:00
15:00

/Exposé en anglais/Talk in english/

A dicolouring of a digraph is a partition of its vertex-set into acyclic subsets. This notion extends the notion of proper colourings of an undirected graph. In the context of digraph recolouring, given a digraph and two of its dicolourings, we wonder if we can transform one into the other by recolouring one vertex at each step while maintaining a dicolouring at any step. Moreover, when such a recolouring sequence exists, we look for the shortest one.

We will consider these questions when dealing with digraphs of bounded maximum degree. In particular, we extend a result due to Feghali et al. and improve this result when restricted to oriented graphs. In order to achieve this, we show a strengthening of the Directed Brooks' Theorem when restricted to this particular class of digraphs.

[Lucas Picasarri-Arrieta] (Université Côte d'Azur )

https://lucaspicasarri.github.io/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178 and https://webconf.math.cnrs.fr/b/mar-zjd-6dz