Décomposition en chemins de Gallai dans les graphes planaires

Abstract

Cette thèse s'inscrit dans le domaine informatique de la théorie des graphes, et traite d'une question posée en 1968 par Tibor Gallai, toujours sans réponse aujourd'hui. Gallai conjectura que les arêtes de tout graphe connexe à n sommets pouvaient être partitionnées en [(n+1)/2] chemins. Bien que cette conjecture fut attaquée et partiellement résolue au fil des ans, la propriété n'a été prouvée que pour des classes de graphes très spécifiques, comme les graphes dont les sommets de degré pair forment une forêt (Pyber, 1996), les graphes de degré maximum 5 (Bonamy, Perrett, 2016) ou les graphes de largeur arborescente au plus 3 (Botler et al., 2018). Les graphes planaires sont les graphes qui peuvent être plongés dans le plan, c'est-à-dire dessinés sans croisements d'arêtes. C'est une classe bien connue dans la théorie des graphes, et largement étudiée. Botler, Jiménez et Sambinelli ont récemment confirmé la conjecture dans le cas des graphes planaires sans triangles.Notre résultat consiste en une preuve de la conjecture sur la classe générale des graphes planaires. Cette classe est notablement plus générale que celles des précédents résultats, et de notre point de vue constitue une importante contribution à l'étude de la conjecture de Gallai. Plus précisément, nous travaillons sur une version plus forte de la conjecture, proposée par Bonamy et Perrett en 2016, et qui énonce que les graphes connexes à n sommets peuvent être décomposés en [n/2] chemins, à l'exception d'une famille de graphes denses. Nous confirmons cette conjecture dans le cas des graphes planaires, en démontrant que tout graphe planaire, à l'exception de K3 et de K5- (K5 moins une arête), peut être décomposé en [n/2] chemins. La preuve est divisée en trois parties : les deux premières montrent le lemme principal de la preuve, qui restreint la structure d'un contre-exemple hypothétique ayant un minimum de sommets, et la troisième partie utilise ce lemme pour montrer qu'un tel contre-exemple n'existe pas.