Publié le 5 juin 2024
–
Mis à jour le 5 juin 2024
Date(s)
le 18 juin 2024
14h00
Lieu(x)
Campus SophiaTech
Centre Inria d'Université Côte d'Azur, salle Euler violet
Thèse financée par l'EUR DS4H
Lucas Picasarri-Arrieta soutiendra sa thèse de doctorat le mardi 18 juin 2024 à 14h00 au Centre Inria d'Université Côte d'Azur dans la salle Euler Violet.
La thèse intitulée « Digraph colouring » a été réalisée dans le pôle Comred sous la direction de 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.
Ce travail a bénéficié d'une aide du gouvernement français, gérée par l'Agence Nationale de la Recherche au titre du Plan d’investissement France 2030, dans le cadre du projet "UCA DS4H" portant la référence n° ANR-17-EURE-0004.
La thèse intitulée « Digraph colouring » a été réalisée dans le pôle Comred sous la direction de 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.
Ce travail a bénéficié d'une aide du gouvernement français, gérée par l'Agence Nationale de la Recherche au titre du Plan d’investissement France 2030, dans le cadre du projet "UCA DS4H" portant la référence n° ANR-17-EURE-0004.
