BEGIN:VCALENDAR VERSION:2.0 PRODID:-//wp-events-plugin.com//7.4.2//EN TZID:Europe/Paris X-WR-TIMEZONE:Europe/Paris BEGIN:VEVENT UID:0-413@lisn.upsaclay.fr DTSTART;TZID=Europe/Paris:20260706T140000 DTEND;TZID=Europe/Paris:20260706T170000 DTSTAMP:20260630T173733Z URL:https://www.lisn.upsaclay.fr/evenements/variations-sur-le-probleme-de- coloration-de-graphes/ SUMMARY:Variations sur le problème de coloration de graphes DESCRIPTION:Jury\nNadia Brauner\, Professeure\, G-SCOP\, Université Grenob le Alpes (présidente)\nDaniel Cranston\, Professeur\, College of William &\; Mary (USA) (rapporteur)\nPaul Dorbec\, Professeur des universités\ , GREYC\, Université de Caen Normandie (rapporteur)\nDaniel Gonçalves\, Chargé de recherche\, LIRMM\, Université Montpellier 2 (examinateur)\nCl éophée Robin\, Maîtresse de conférences\, IRIF\, Université Paris Cit é (examinatrice)\nRésumé\nLe problème de coloration propre est un suje t fondamental en théorie des graphes\; non seulement les colorations prop res présentent une complexité fascinante en tant qu'objets combinatoires \, mais elles apparaissent également dans un large éventail d'applicatio ns\, 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 o u le relâchement de contraintes. Cette thèse étudie les aspects extrém aux 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 identi fiant la structure des graphes dans les cas limites.\nLe premier chapitre explore une généralisation de la coloration propre via des contraintes m ultichromatiques. 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 da ns ce cadre\; nous considérons en particulier la coloration frugale et la coloration acyclique. L’étude du nombre chromatique dans les graphes d e degré borné excluant certains sous-graphes est depuis longtemps un suj et de recherche actif\; nous étendons cette étude à la notion plus gén érale des nombres chromatiques P-évitant en obtenant des bornes extréma les en fonction du degré maximum et des sous-graphes interdits.\nLe deuxi ème chapitre examine la notion de coloration propre «sans conflit»\, qu i requiert que chaque voisinage ouvert contienne au moins une couleur soli taire. 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élio rons cette borne supérieure en montrant que seulement ∆ + O(log ∆) co uleurs suffisent. Notre méthode s’étend à la notion plus générale d e coloration propre h-sans-conflit (h ≥ 1)\, qui constitue une interpola tion naturelle entre la coloration propre et la coloration à distance 2. Nous considérons aussi la notion de coloration sans conflit dans les hype rgraphes\, pour laquelle nous prouvons une borne de type Reed dès lors qu e l'hypergraphe ne contient pas de voisinage dense pour les arêtes de tai lle 2.\nLe troisième chapitre est consacré à la notion de coloration do minante\, 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 croissant e 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 cl asses 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 éto iles 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 t ous 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 pou r des graphes de grande maille. CATEGORIES:Thèses et HDR LOCATION:LISN Site Plaine – Digitéo\, 1 rue René THOM 91190 Gif-sur -Yvette\, France X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=1 rue René THOM 91190 Gif- sur-Yvette\, France;X-APPLE-RADIUS=100;X-TITLE=LISN Site Plaine – Digit éo:geo:0,0 END:VEVENT BEGIN:VTIMEZONE TZID:Europe/Paris X-LIC-LOCATION:Europe/Paris BEGIN:DAYLIGHT DTSTART:20260329T030000 TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST END:DAYLIGHT END:VTIMEZONE END:VCALENDAR