Variations sur le problème de coloration de graphes

Jury

• Nadia Brauner, Professeure, G-SCOP, Université Grenoble Alpes (présidente)
• Daniel Cranston, Professeur, College of William & Mary (USA) (rapporteur)
• Paul Dorbec, Professeur des universités, GREYC, Université de Caen Normandie (rapporteur)
• Daniel Gonçalves, Chargé de recherche, LIRMMLaboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier, Université Montpellier 2 (examinateur)
• Cléophée Robin, Maîtresse de conférences, IRIF, Université Paris Cité (examinatrice)

Résumé

Le problème de coloration propre est un sujet fondamental en théorie des graphes; non seulement les colorations propres présentent une complexité fascinante en tant qu’objets combinatoires, mais elles apparaissent également dans un large éventail d’applications, notamment parmi les problèmes d’allocation de ressources. Cependant, certaines applications spécifiques peuvent nécessiter des formulations légèrement différentes du problème de coloration propre par l’ajout ou le relâchement de contraintes. Cette thèse étudie les aspects extrémaux de trois variations sur le problème de coloration propre en étudiant les bornes générales sur la taille des solutions optimales et en identifiant la structure des graphes dans les cas limites.

Le premier chapitre explore une généralisation de la coloration propre via des contraintes multichromatiques. Un motif est un graphe dont les sommets sont colorés. Étant donnée une famille P de motifs, une coloration P-évitante d’un graphe G est une coloration des sommets de G telle qu’aucun motif de P n’apparaît comme sous-graphe coloré dans G (à renommage des couleurs près). On récupère la notion de coloration propre lorsque P contient précisement l’arête monochromatique, et de nombreuses variantes très étudiées de la coloration propre peuvent être décrites et unifiées dans ce cadre; nous considérons en particulier la coloration frugale et la coloration acyclique. L’étude du nombre chromatique dans les graphes de degré borné excluant certains sous-graphes est depuis longtemps un sujet de recherche actif; nous étendons cette étude à la notion plus générale des nombres chromatiques P-évitant en obtenant des bornes extrémales en fonction du degré maximum et des sous-graphes interdits.

Le deuxième chapitre examine la notion de coloration propre «sans conflit», qui requiert que chaque voisinage ouvert contienne au moins une couleur solitaire. Caro et al. ont conjecturé que pour chaque graphe connexe de degré maximum ∆ ≥ 3, il existe une coloration propre sans conflit avec ∆+1 couleurs. Liu et Reed ont prouvé cette conjecture asymptotiquement en montrant que ∆ + O(∆^{2/3} log∆) couleurs suffisent. Nous améliorons cette borne supérieure en montrant que seulement ∆ + O(log ∆) couleurs suffisent. Notre méthode s’étend à la notion plus générale de coloration propre h-sans-conflit (h ≥ 1), qui constitue une interpolation naturelle entre la coloration propre et la coloration à distance 2. Nous considérons aussi la notion de coloration sans conflit dans les hypergraphes, pour laquelle nous prouvons une borne de type Reed dès lors que l’hypergraphe ne contient pas de voisinage dense pour les arêtes de taille 2.

Le troisième chapitre est consacré à la notion de coloration dominante, où les classes de couleurs sont des ensembles dominants et l’on cherche à maximiser le nombre de couleurs utilisées; ce maximum est appelé le nombre domatique. Il est facile d’observer que si G a degré minimum δ, alors le nombre domatique de G est au plus δ+1. On dit qu’une classe de graphes est dom-bornée s’il existe une fonction croissante non bornée f telle que tout graphe G de cette classe a nombre domatique au moins f(δ(G)). Zelinka a montré que la classe de tous les graphes n’est pas dom-bornée, aussi nous intéressons-nous à identifier des classes naturelles de graphes qui le sont. Par analogie avec une conjecture de Gyárfás (1975) et Sumner (1981), nous conjecturons que la classe des graphes sans copie induite de H est dom-bornée lorsque H est un arbre de diamètre au plus 3. Nous prouvons notre conjecture pour les cas des étoiles et du chemin à 4 sommets. Nous considérons également la relaxation fractionnaire du problème de coloration dominante; en répondant à une conjecture de Gadouleau et al. sous une forme forte, nous montrons que tous les graphes connexes de degré minimum 2 ayant au moins 8 sommets ont nombre domatique fractionnaire au moins 5/2, ce qui est optimal même pour des graphes de grande maille.