W&M Homepage
This calendar presented by
William & Mary
[PAST EVENT] Colloquium talk/CSUMS lecture
November 2, 2012
2pm - 3pm
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
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