Le but de cette thèse est d'étudier l'évolution et la robustesse de certains paramètres de graphes face à des attaques.
Le nombre chromatique d'un graphe est l'un des paramètres les plus étudiés en théorie des graphes : il s'agit de trouver le plus petit nombre de couleurs tel qu'il soit possible de colorier les sommets d'un graphe sans que deux sommets adjacents ne soient de la même couleur. Un algorithme assez naturel pour colorier un graphe est de choisir les sommets dans un certain ordre et de les colorier à chaque fois avec la plus petite couleur disponible. Cela ne donne pas toujours la meilleure coloration puisque le problème est NP-complet mais on sait qu'il existe un ordre amenant à une coloration optimale. Un ordre peut aussi amener à des colorations très mauvaises et le nombre chromatique de Grundy d'un graphe est le nombre de couleurs nécessaires obtenu dans le pire cas. Une autre façon de voir ce paramètre est de considérer qu'un attaquant nous donne les sommets dans un certain ordre de façon à ce que l'on ait besoin d'un grand nombre de couleurs. Le nombre chromatique de Grundy nous assure alors que l'on ne dépassera pas cette valeur.
Il existe d'autres façons de construire une coloration d'un graphe avec un adversaire, comme la coloration ludique de graphes, née dans les années 1990, suite aux travaux de Bodlaender. Dans ce problème, à tour de rôle, Alice et Bob colorient proprement les sommets d'un graphe, avec des objectifs contraires: Alice doit colorier le graphe en entier et Bob doit l'en empêcher. Le nombre chromatique ludique est le plus petit nombre de couleurs pour lequel Alice gagne à coup sûr. Dans la littérature, ce type de jeu sur les graphes est actuellement très prisé et a fait l'objet de nombreuses variantes définies à partir d'autres problèmes connus de théorie des graphes. Ce type de jeu modélise assez bien les problématiques de sécurité dans les réseaux, où l'on imagine Bob comme cherchant à casser la stabilité d'un système (stabilité qui doit quant à elle être garantie par Alice).
Dans un premier temps, l'étudiant sera amené à étudier les résultats existants en termes de coloration de Grundy, de coloration ludique et de variantes similaires comme la coloration ludique de Grundy. Des encadrements plus précis des paramètres existants sont attendus sur certaines classes de graphes, comme les graphes planaires, les graphes d'intervalles, les graphes puissances et les graphes réguliers. D’autres variantes de coloration de Grundy sont également étudiés comme la coloration Grundy partielle où la propriété de Grundy n’est satisfaite que pour un sous-ensemble de sommets du graphe. En particulier, une étude des cas extrémaux sera menée, afin de caractériser l'ensemble des graphes pour lesquels les bornes connues de ces paramètres sont atteintes.
Pour la suite de la thèse, ces premiers travaux et une bonne connaissance de l'état de l'art permettront d'étudier d'autres paramètres de graphes sous ces aspects-là. Cela a par exemple été récemment le cas pour le nombre ludique de domination ou les codes identifiants adaptatifs. De nombreuses questions restent ouvertes suite à l'introduction de ces notions.
Les résultats attendus pour cette thèse sont les suivants:
- complexité algorithmique théorique des calculs de paramètres Grundy ou ludiques.
- calculs de valeurs exactes de paramètres Grundy ou ludiques pour certaines familles de
graphes.
- analogues de résultats connus de coloration/domination de graphes en version attaquée.