W&M Featured Events
[PAST EVENT] Mathematics Colloquium: Songling Shan (Illinois State University)
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.