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 Rk(G), is the graph whose vertices are the k-colorings of G and two colorings are adjacent in Rk(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 Rk(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 Rl(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 P4 or P3+P1. 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 2K2-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 P5-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.

Convocation Year

2024

Download

Share

COinS