This Ph.D. thesis explores the structure of solution spaces through combinatorial reconfiguration. Unlike the classical approach, which focuses on the existence or optimization of a solution for a given problem, reconfiguration studies the entire space formed by the set of feasible solutions, called configurations. These solutions are linked together via elementary local modifications, which allows one to model this space as a reconfiguration graph.
A central problem then consists of determining whether a configuration can be transformed into another by following these modifications while staying within the set of feasible solutions; that is, finding a path between two given configurations in the reconfiguration graph.
In this manuscript, we specifically focus on reconfiguration problems in graph theory.

The first part of the thesis is devoted to the reconfiguration of graph colorings. We primarily study two transition rules: single-vertex recoloring and Kempe changes.
Motivated by the random sampling of proper colorings, we first analyze a probabilistic algorithm based on a hill-climbing method using single-vertex recoloring.
We prove its termination for edge-colorings. Still focusing on single-vertex recoloring, we then study the diameter of the reconfiguration graph of list-colorings when its connectivity is guaranteed. 
Finally, under the Kempe changes rule, we explore the number of colors required to ensure the connectivity of the reconfiguration graph.

The second part investigates the reconfiguration of independent sets, where we aim to transform one independent set into another by changing one vertex at each step.
In general, this problem is PSPACE-complete, even on highly restricted graph classes. 
However, when parameterized by the size of the independent set, it becomes FPT on sparse graph classes, in particular for graphs of bounded treewidth and beyond.
Our main contribution here is to show that, within this class, the problem admits a linear kernel. 
In other words, any instance of the problem can be reduced to an equivalent instance whose size is strictly proportional to the size of the independent sets.

Finally, the last part explores a problem of a more geometric nature: the reconfiguration of plane trees (without crossings) spanning a set of points in convex position.
It is known that any such tree can be transformed into another via edge flips, but the exact number of necessary flips remains hard to determine.
Given two such trees, we establish lower and upper bounds on the number of flips required to transform one into the other.