Graph Coloring and Recoloring

Coloration et recoloration de graphes Cette thèse s'inscrit dans le cadre de la théorie des graphes, et plus précisément dans le cadre de la coloration de graphes avec une attention particulière portée à la coloration d'arêtes, et la reconfiguration de colorations. Dans cette thèse, nous étudions principalement les changements de Kempe, un outil de transformation locale d'une coloration en une autre coloration. Ce concept est une idée clef de la preuve du théorème des 4 couleurs. Nous donnons un aperçu de l'histoire de cet outil technique, décrivons la manière dont il est devenu l'un des outils les plus prolifiques quant aux questions de colorations de graphes, et présentons des questions, s'inscrivant dans le cadre plus général de la reconfiguration combinatoire, issues de ce concept.Nous présentons ensuite nos résultats sur la coloration gloutonne d'arêtes et la reconfiguration de coloration de sommets pour les graphes sans K_t comme mineurs. En ce qui concerne la reconfiguration de coloration d'arêtes, nous prouvons en particulier que toutes les (chi'(G)+1)-colorations sont Kempe-équivalentes entre elles (i.e. qu'il est possible de transformer n'importe quelle coloration en n'importe quelle autre coloration en utilisant uniquement des changements de Kempe), prouvant ainsi une conjecture de Vizing de 1965. Nous présentons enfin notre travail sur la coloration de sommets de graphes signés, et sur la coloration d'arêtes de graphes planaires sans triangle de degré maximum 4.