Jonathan Narboni's thesis: "Coloring and recoloring of graphs"

This thesis is based on graph theory, and more precisely on graph coloring, with a particular focus on edge coloring and reconfiguration of colorings. In this thesis, we mainly study Kempe changes, a tool for local transformation of a coloring into another coloring. This concept is a key idea in the proof of the $4$ color theorem. We give an overview of the history of this technical tool, describe how it has become one of the most prolific tools for graph coloring issues, and present questions, in the more general framework of combinatorial reconfiguration, arising from this concept. We then present our results on gluttonous edge coloring and vertex coloring reconfiguration for graphs without $K_t$ as a minor. Concerning edge reconfiguration, we prove in particular that all $(chi'(G)+1)$-colors are Kempe-equivalent to each other (i.e. it is possible to transform any coloring into any other coloring using only Kempe changes), thus proving a Vizing conjecture from 1965. Finally, we present our work on the coloring of vertices of signed graphs, and on the coloring of edges of planar graphs without triangle of maximum degree $4$.

Amphi LaBRI