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