Average degrees of edge-chromatic critical graphs

Abstract

Given a graph $G$, denote by $\Delta$, $\bar{d}$ and ${\chi }^{\prime }$ the maximum degree, the average degree and the chromatic index of $G$, respectively. A simple graph $G$ is called {\it edge-$\Delta$-critical} if ${\chi }^{\prime }(G)=\Delta +1$ and ${\chi }^{\prime }(H)\le \Delta$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is edge-$\Delta$-critical, then $\bar{d}\ge \Delta -1+\frac{3}{n}$. We show that $$ \begin{displaystyle} \avd \ge \begin{cases} 0.69241\D-0.15658 \quad\,\: \mbox{ if } Δ\geq 66, 0.69392\D-0.20642\quad\;\,\mbox{ if } Δ=65, \mbox{ and } 0.68706\D+0.19815\quad\! \quad\mbox{if } 56\leq Δ\leq64. \end{cases} \end{displaystyle} $$ This result improves the best known bound $\frac{2}{3}(\Delta +2)$ obtained by Woodall in 2007 for $\Delta \ge 56$. Additionally, Woodall constructed an infinite family of graphs showing his result cannot be improved by well-known Vizing's Adjacency Lemma and other known edge-coloring techniques. To over come the barrier, we follow the recently developed recoloring technique of Tashkinov trees to expand Vizing fans technique to a larger class of trees.

23 pages