Problèmes structuraux et extrémaux liés à la coloration des graphes sommet- ou arête-coloriés

Jury

• Guantao Chen – Professeure, Department of Mathematics and Statistics, Georgia State University – Rapporteur & Examinateur
• Xujin Chen – Professeure, Academy of Mathematics and Systems Science, Chinese Academy of Sciences – Examinatrice
• Louis Esperet – Directeur de recherche CNRS, Sciences pour la Conception, l’Optimisation et la Production, Université Grenoble Alpes – Rapporteur & Examinateur
• Baogang Xu – Professeure, School of Mathematical Sciences, Nanjing Normal 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

Résumé

La coloration de graphes est l’un des sujets les plus connus, populaires et largement étudiés dans le domaine de la théorie des graphes, avec une vaste littérature comprenant des approches provenant de nombreux domaines ainsi que de nombreux problèmes qui sont encore ouverts et étudiés par divers mathématiciens et informaticiens à travers le monde. Tout d’abord, dans cette thèse, nous visons à optimiser la stratégie de coloration des sommets de graphes et d’hypergraphes avec certaines contraintes données, en combinant le concept de coloration propre et d’élément représentatif de certains sous-ensembles de sommets. D’autre part, en fonction du sujet à colorer, une grande quantité de recherches et de problèmes de graphes à arêtes colorées ont émergé, avec des applications importantes en biologie et en technologies web. Nous fournissons quelques résultats analogues pour certaines questions de connectivité, afin de décrire des graphes dont les arêtes sont attribuées suffisamment de couleurs, garantissant ainsi des arbres couvrants ou des cycles ayant une structure chromatique spécifique.

Mots clés : Coloration propre; Coloration impaire; Hypergraphe; Graphe à arêtes colorées; Extensibilité des cycles; Nombre anti-Ramsey; Sous-graphe proprement coloré; Arbre couvrant faiblement propre.