Certains problèmes de coloration des sommets et une généralisation de la Hamilton-connectivité dans des graphes. (Some vertex colouring problems and a generalisation of Hamilton-connectivity in graphs)

La décomposition des graphes fait référence au processus de décomposer un graphe complexe en composantes plus simples et plus petites, souvent dans le but d’analyser ou de résoudre des problèmes liés au graphe. Il s’agit d’un outil important pour représenter la structure globale et les propriétés d’une manière plus détaillée. Il est aussi également utile pour résoudre des problèmes impliquant la recherche de structures spécifiques dans un graphe. Il existe plusieurs types courants de techniques de décomposition de graphe largement utilisées en théorie des graphes et dans des domaines connexes, notamment la décomposition en arbres, la décomposition en blocs, la décomposition modulaire, la décomposition hiérarchique, etc. Cette thèse étudie deux types de décomposition de sommets d’un graphe : les colorations propres (décomposition en ensembles indépendants) et la Hamilton-connectivité (décomposition en chemins internement disjoints entre deux ensembles où les chemins couvrent tous les sommets du graphe).

Mots clés :  Graphes planaires extérieurs 2-connexes; Graphes sans triangle; DP-colorations; Colorations fractionnaire; Hamilton-connectivité; Degré maximum; Somme des degrés.

Composition du jury

• Zdeněk DVOŘÁK- Professeure, Charles University- Rapporteur & Examinateur
• Hong LIU – Chercheur distingué en recherche,  Institute for Basic Science  (IBS)- Rapporteur & Examinateur
• Liying KANG- Professeure, Shanghai University –  Examinatrice
• Shenggui ZHANG- Professeure, Northwestern Polytechnical University – Examinateur
• Hao LI – Directeur de recherche, CNRS – Directeur de thèse
• François PIROT – Maître de Conférences, Université Paris-Saclay – Co-encadrant de thèse