Speaker: Songling Shan
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 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 to their chromatic index, we naturally classify all simple graphs into class 1 (those with chromatic index equal to their maximum degree) or class 2, but the classification problem is NP-complete. However, when a graph 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 look at some recent progress toward the conjecture.
