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)leDelta$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is edge-$Delta$-critical, then $bar{d}geq Delta-1+ frac{3}{n}$. We show that $$ begin{displaystyle} avd ge begin{cases} 0.69241D-0.15658 quad,: mbox{ if } Deltageq 66, 0.69392D-0.20642quad;,mbox{ if } Delta=65, mbox{ and } 0.68706D+0.19815quad! quadmbox{if } 56leq Deltaleq64. end{cases} end{displaystyle} $$ This result improves the best known bound $frac{2}{3}(Delta +2)$ obtained by Woodall in 2007 for $Delta geq 56$. Additionally, Woodall constructed an infinite family of graphs showing his result cannot be improved by well-known Vizings 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.
Download