Nov 11, 2022
Contact: Gexin Yu
Summary
{{https://about.illinoisstate.edu/sshan12/, Songling Shan}} (Illinois State University)
Full Description
Title: Graph edge coloring and the Overfull Conjecture
Abstract: 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.
