[PAST EVENT] Mathematics Colloquium:  Songling Shan (Illinois State University)

November 11, 2022
2pm - 3pm
Location
Jones Hall, Room 301
200 Ukrop Way
Williamsburg, VA 23185Map this location
Access & Features
  • Free food
  • Open to the public

Graph edge coloring and the Overfull Conjecture

Let $G$ be a simple graph. An edge coloring of $G$ is an assignment of colors to the edges of $G$ so that any two adjacent edges receive distinct colors. The least number of colors in such an assignment is called the chromatic index of $G$.

Clearly, we need at least $\Delta(G)$, the maximum degree of $G$, this number of colors. On the other hand, Vizing in 1965 proved that at most $\Delta(G)+1$ colors are sufficient. According its chromatic index, all simple graphs are naturally classified into class 1 (those with its chromatic index equal its maximum degree) or class 2 but the classification problem is NP-complete. However, when a graph simply has “too many” edges, the graph is trivially class 2. Conversely, Chetwynd and Hilton in 1985 made the Overfull Conjecture: if a graph $G$ has its maximum degree large, then $G$ is class 2 also implies that $G$ or some subgraph of $G$ has too many edges. In this talk, we will survey some recent progress towards the conjecture.

Refreshments will begin at 1:30 pm outside Jones 100.