Recruitment Talk -- Graph edge coloring and the Overfull Conjecture

Image
January 30, 2023
4:15PM - 5:15PM
Location
CH 240

Date Range
Add to Calendar 2023-01-30 16:15:00 2023-01-30 17:15:00 Recruitment Talk -- Graph edge coloring and the Overfull Conjecture 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. CH 240 Department of Mathematics math@osu.edu America/New_York public
Description

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.

Events Filters: