Presented By: Student Combinatorics Seminar - Department of Mathematics
Edge-Kempe equivalence classes of 3-regular graphs
Veronica Lang
In his proposed proof of the Four Color Theorem in 1879, Alfred Bray Kempe introduced an operation on edge colorings of a graph which is now known as an edge-Kempe switch. An edge-Kempe switch swaps the two colors on a maximal two-color chain of edges, and these moves partition the edge colorings of a graph into edge-Kempe equivalence classes. Ruth Haas and sarah-marie belcastro proved that a 3-regular, 3-edge-colored, planar, bipartite graph has one edge-Kempe equivalence class. In this talk, we will discuss that proof and speculate on its applications to webs. We will also count the edge-Kempe equivalence classes of some nonplanar, bipartite, 3-regular graphs.