## Document Type

Thesis

## Degree Name

Doctor of Philosophy (PhD)

## Department

Mathematics

## Program Name/Specialization

Mathematics for Science and Finance

## Faculty/School

Faculty of Science

## First Advisor

Kathie Cameron

## Advisor Role

Advisor

## Abstract

In this thesis we study reconfiguration problems in graph theory. A reconfiguration problem is generally defined on the solution space of a problem for which a configuration can be defined as a feasible solution, for example, a coloring of a graph. In Chapters 1 through 4 we study the reconfiguration of vertex colorings. The reconfiguration graph of the *k*-colorings, denoted *R _{k}*(

*G*), is the graph whose vertices are the

*k*-colorings of G and two colorings are adjacent in

*R*(

_{k}*G*) if they differ on exactly one vertex. The basic question investigated here can be phrased as follows: Given a graph

*G*and two

*k*-colorings of

*G*, can we transform one into the other by changing the color of one vertex at a time while maintaining a proper coloring at each step.

A graph *G* is said to be *k*-mixing if *R _{k}*(

*G*) is connected and said to be recolorable if

*G*is

*l*-mixing for all

*l*larger than the chromatic number of

*G*. The

*l*-recoloring diameter of a graph

*G*is the diameter of the reconfiguration graph

*R*(

_{l}*G*). Several attempts have been made to study the recolorability of graphs defined by forbidden induced subgraphs. We prove that, for a fixed graph

*H*, every

*H*-free graph is recolorable if and only if

*H*is an induced subgraph of

*P*

_{4}or

*P*

_{3}+

*P*

_{1}. We also start an investigation into this problem for classes of graphs defined by two forbidden induced subgraphs. In Section 3.3 and Section 3.4, we study the problem for subclasses of triangle-free graphs and 2

*K*

_{2}-free graphs, respectively.

In Chapter 4, we develop techniques to use the modular decomposition of a graph to prove that it is recolorable. We apply these techniques to study recolorability of several subclasses of *P*_{5}-free graphs.

In Chapter 5, we study reconfiguration in tournaments. We define an independent set in a tournament as a set of vertices which induce a transitive subtournament. We prove that deciding whether we can transform one independent set of a tournament to another independent set under token addition and removal is PSPACE-complete. In Sections 5.3 and 5.4 we study reconfiguration of independent sets in tournaments under the token sliding model.

## Recommended Citation

Belavadi, Manoj, "Recoloring in Hereditary Graph Classes: Structure and Decomposition" (2024). *Theses and Dissertations (Comprehensive)*. 2718.

https://scholars.wlu.ca/etd/2718

## Convocation Year

2024