Published on June 5, 2024
–
Updated on June 5, 2024
Dates
on the June 18, 2024
14h00
Location
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.
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.
