[PAST EVENT] Colloquium talk/CSUMS lecture

November 2, 2012
2pm - 3pm
Jones Hall, Room 301
200 Ukrop Way
Williamsburg, VA 23185Map this location
A graph is a set of vertices and a set of edges that connect pairs of vertices. An edge coloring of a graph is an assignment of colors to the edges of the graph so that any two edges sharing a common endvertex receive different colors.

Edge coloring was first studied by Tait in 1880 as an approach to attack the well-known Map 4-Coloring conjecture. Vizing's theorem classifies the simple graphs into two classes, Class one graphs and Class two graphs. However, it is NP-hard to determine whether a graph is in Class one or two. In the late 1960s, Vizing proposed several conjectures to study the "barely" Class two graphs (critical graphs). Those conjectures are fundamental problems in the area of edge coloring. In the last 10 years, there was a lot of progress on those conjectures.

In this talk, I will first talk about the relation between Map Coloring and Edge Coloring and then survey the progress on Vizing's conjectures