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.

Comments

Department: Mathematics

Faculty Mentor: Dr. Heather Russell

Share

COinS
 

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.