Thèses Félix KLINGELHOEFER

Algorithmes pour des Problèmes de Coloration avec Promesse sur les Tournois et les Graphes

Résumé

La première partie de cette thèse porte sur le sujet de la coloration de tournois, sous l'angle de l'algorithmie, de la complexité et de la structure. Une k-coloration d'un graphe orienté, et en particulier d'un tournoi, est une partition de ses sommets en k ensembles acycliques. Le nombre chromatique d'un graphe orienté ou d'un tournoi est alors le plus petit k tel que le graphe puisse être k-coloré. Décider si un tournoi peut être 2-coloré est déjà NP-difficile. Un problème naturel, similaire à celui de la coloration d'un graphe 3-colorable avec peu de couleurs,est de colorer un tournoi 2-colorable avec peu de couleurs. Ce problème ne semble pas avoir été abordé auparavant, bien qu'il s'agisse d'un cas particulier de la coloration d'un hypergraphe 3-uniforme 2-colorable avec peu de couleurs, problème bien étudié avec des bornes inférieures super-constantes. Nous présentons un lemme de décomposition efficace pour les tournois et montrons qu'il peut être utilisé pour concevoir des algorithmes en temps polynomial pour colorer différentes classes de tournois avec peu de couleurs, notamment un algorithme pour colorer un tournoi 2-colorable avec dix couleurs. Pour les classes de tournois considérées, nous complétons nos bornes supérieures par des bornes inférieures renforcées, offrant ainsi une vision complète des aspects algorithmiques et de complexité de la coloration des tournois. Nous étendons ensuite nos résultats à différentes classes de tournois et de graphes orientés. Le voisinage d'un arc uv dans un tournoi T est l'ensemble de sommets qui forment un triangle orienté avec l'arc uv. En utilisant notre lemme de décomposition, nous montrons que si le voisinage de chaque arc dans un tournoi a un nombre chromatique borné, alors tout le tournoi a un nombre chromatique borné. Ceci est également vrai de manière plus générale pour les graphes orientés avec un nombre d'indépendance borné, et nous étendons notre preuve pour les tournois à cette classe de graphes orientés denses. En tant qu'application, nous démontrons l'équivalence d'une conjecture d'El-Zahar et Erdős et d'une conjecture récente de Nguyen, Scott et Seymour concernant la structure des graphes et des tournois avec un grand nombre chromatique.

Dans la deuxième partie de cette thèse, nous nous concentrons sur le problème de la recherche de stables maximums dans la classe des graphes Cycle-plus-Triangles. Un graphe Cycle-plus-Triangles est l'union disjointe de t triangles et d'un cycle Hamiltonien sur les 3t sommets. Il est 3-colorable, et nous présentons un aperçu des différentes preuves de sa 3-colorabilité. Cependant, il n'existe pas d'algorithme efficace connu pour trouver une 3-coloration ou même pour 
trouver un ensemble stable maximum (c'est-à-dire un stable de taille t). Nous présentons un algorithme aléatoire simple qui produit un ensemble stable maximum lorsqu'il termine. Nous émettons l'hypothèse que pour toute instance de Cycle-plus-Triangles, notre algorithme s'achève en temps polynomial attendu. Dans une démarche (non fructueuse) visant à trouver des instances difficiles pour notre algorithme, nous discutons de la structure et des propriétés des instances de Cycle-plus-Triangles et des méthodes pour les générer. Enfin, nous examinons le comportement de ces algorithmes sur des problèmes connexes, tels que la 3-coloration ou la recherche d'ensembles indépendants maximums dans une classe plus générale de graphes.