Thesis Defense - Lucas Picasarri-Arrieta - Digraph Colouring

  • IDEX
  • Research
Published on June 5, 2024 Updated on June 5, 2024

on the June 18, 2024

Inria, room Euler violet

Funded by DS4H Graduate School

This thesis has been conducted in the COMRED team and supervized by Frédéric Havet.

Abstract  :
Erdős and Neumann-Lara introduced a notion of colouring of digraphs in the late 1970s, namely the dicolouring, and its associated digraph parameter: the dichromatic number.  It appears in the last decades that many classical results on graph colouring have directed counterparts using these notions. This thesis focuses on both the extension of graph colouring results to digraphs, and their possible strengthenings on specific class of digraphs. In particular, we study directed analogues of Brooks' theorem, density and structure of critical graphs, and reconfiguration of graph colourings.

This work has been supported by the French government, through the France 2030 investment plan managed by the Agence Nationale de la Recherche, as part of the "UCA DS4H" project, reference ANR-17-EURE-0004.