Reconfiguration of Graph Colorings

Reconfiguration of Graph Colorings

Zeven, Koen (TU Delft Electrical Engineering, Mathematics and Computer Science)

Cames van Batenburg, W.P.S. (mentor)
Bishnoi, A. (mentor)

Delft University of Technology

Applied Mathematics

2023-07-19

For this thesis, we consider two $k$-colorings of a graph $G$ adjacent if one can recolor one into the other by changing the color of one vertex. The reconfiguration graph of a graph $G$ on $k$ colors $\mathcal{C}_{k}(G)$ is the graph for which the vertices are the $k$-colorings of $G$, and an edge is between two $k$-colorings if they are adjacent. We further investigate the diameter of the reconfiguration graph on $k$ colors: $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$. 
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs.

graph theory
graph coloring
reconfiguration
diameter
complete r-partite graphs
r-partite
lower bound
matching

http://resolver.tudelft.nl/uuid:43108b69-8da3-4a86-b3aa-c4091c13139e

Student theses

bachelor thesis

© 2023 Koen Zeven