Off-campus University of Richmond users: To download campus access theses, please use the following link to log in to our proxy server with your university username and password.

Date of Award

2020

Document Type

Restricted Thesis: Campus only access

Degree Name

Bachelor of Science

Department

Mathematical Economics

First Advisor

Dr. Heather M. Russell

Abstract

Any graph G can be k-colored by assigning a color c 2 {1, 2, . . . , k} to each vertex of G. We say that a k-coloring is proper is all pairs of adjacent vertices have distinct colors. From the set of all k-colorings of G, we can construct a k-coloring graph Ck(G) such that two k-colorings are adjacent if their colorings differ by exactly one vertex in G. Coloring graphs are one example of a larger class of problems called reconfiguration systems, which can be used to study the structure of the set of all solutions for a given problem. In this thesis, we first present some motivating examples of coloring graphs from the literature and their analyze properties. Then, we consider the connectivity of k-coloring graphs. In particular, we observed a central biconnected component present in all connected coloring graphs that we call the mothership. We prove the existence and uniqueness of this component for connected coloring graphs and begin to characterize what colorings lie in the mothership. Finally, we will introduce the future directions of the project which include continuing to determine which colorings lie in the mothership as well as defining a mothership for a disconnected coloring graph.

Download

Share

COinS