Discrete Mathematics Seminar 

Speaker: Songling Shan
Title: Towards the Overfull Conjecture
Abstract: Let $G$ be a simple graph with maximum degree $\Delta(G)$. A subgraph $H\subseteq G$ is \emph{$\Delta(G)$-overfull} if $|E(H)|>\Delta(G)\left\lfloor |V(H)|/2\right\rfloor$. In any edge coloring of $G$, each color class restricted to $H$ is a matching of size at most $\left\lfloor |V(H)|/2\right\rfloor$. Thus, if $G$ contains a $\Delta(G)$-overfull subgraph, then $G$ cannot be edge-colored with only $\Delta(G)$ colors. By Vizing’s Theorem, $\chi'(G)\le \Delta(G)+1$, and hence $G$ is class $2$. In 1986, Chetwynd and Hilton conjectured that whenever $\Delta(G)>|V(G)|/3$, the converse also holds: every class $2$ graph $G$ contains a $\Delta(G)$-overfull subgraph. This statement, commonly known as the \emph{Overfull Conjecture}, is one of the most influential conjectures in graph edge coloring. It would imply a polynomial-time algorithm for determining the chromatic index of graphs $G$ with $\Delta(G)>|V(G)|/3$, and would also imply several other longstanding conjectures in the area, including the Just-overfull Conjecture and the Vertex-splitting Conjecture. In previous work, Shan verified the conjecture for large graphs $G$ with maximum degree at least $13|V(G)|/14$. Here, we confirm the conjecture for robust expanders satisfying certain density constraints. As a consequence, for every $0<\ve<1$, the conjecture holds for all sufficiently large graphs $G$ with maximum degree at least $(1+\ve)|V(G)|/2$. Joint work with Guantao Chen and Jessica McDonald.