#### Event Title

#### Location

University of Richmond, Richmond, Virginia

#### Document Type

Slide Presentation (UR Campus Only)

#### Description

A *graph* G is a collection of vertices connected by edges. A *k-coloring* of G assigns a color c in {1,...,k} to each vertex. This coloring is *proper* if for all v in V[G], the color of v is different from the colors of all vertices that share an edge with v. Then we can let the set of all proper k-colorings of G be a vertex set and build a coloring graph C_k(G) where two vertices are adjacent if the associated colorings differ by exactly one vertex. In my research, I was particularly interested in building on previous results to further understand the connected structure of coloring graphs.

Using software developed by Professor Bhakta and several students, my research group identified a central, biconnected component present in all connected coloring graphs. We named this component the mothership and began to rigorously define it and prove its existence. In this presentation, I will discuss my contributions to our work including my proofs of a sequence of lemmas that establish the uniqueness and existence of the mothership. Then, I will conclude with a brief note about our current and future research directions.

Connectivity of Coloring Graphs

University of Richmond, Richmond, Virginia

A *graph* G is a collection of vertices connected by edges. A *k-coloring* of G assigns a color c in {1,...,k} to each vertex. This coloring is *proper* if for all v in V[G], the color of v is different from the colors of all vertices that share an edge with v. Then we can let the set of all proper k-colorings of G be a vertex set and build a coloring graph C_k(G) where two vertices are adjacent if the associated colorings differ by exactly one vertex. In my research, I was particularly interested in building on previous results to further understand the connected structure of coloring graphs.

Using software developed by Professor Bhakta and several students, my research group identified a central, biconnected component present in all connected coloring graphs. We named this component the mothership and began to rigorously define it and prove its existence. In this presentation, I will discuss my contributions to our work including my proofs of a sequence of lemmas that establish the uniqueness and existence of the mothership. Then, I will conclude with a brief note about our current and future research directions.

## Comments

Department: Mathematics

Faculty Mentor: Dr. Heather Russell