Independence number of edge-chromatic critical graphs

Abstract

Let $G$ be a simple graph with maximum degree $\Delta (G)$ and chromatic index ${\chi }^{\prime }(G)$. A classic result of Vizing indicates that either ${\chi }^{\prime }(G)=\Delta (G)$ or ${\chi }^{\prime }(G)=\Delta (G)+1$. The graph $G$ is called $\Delta$-critical if $G$ is connected, ${\chi }^{\prime }(G)=\Delta (G)+1$ and for any $e\in E(G)$, ${\chi }^{\prime }(G-e)=\Delta (G)$. Let $G$ be an $n$-vertex $\Delta$-critical graph. Vizing conjectured that $\alpha (G)$, the independence number of $G$, is at most $\frac{n}{2}$. The current best result on this conjecture, shown by Woodall, is that $\alpha (G)<\frac{3n}{5}$. We show that for any given $\epsilon \in (0,1)$, there exist positive constants $d_0(\epsilon )$ and $D_0(\epsilon )$ such that if $G$ is an $n$-vertex $\Delta$-critical graph with minimum degree at least $d_0$ and maximum degree at least $D_0$, then $\alpha (G)<(\frac{1}{2}+\epsilon )n$. In particular, we show that if $G$ is an $n$-vertex $\Delta$-critical graph with minimum degree at least $d$ and $\Delta (G)\ge (d+2{)}^{5d+10}$, then \[ α(G) < \left. \begin{cases} \frac{7n}{12}, & \text{if $d=3$; } \frac{4n}{7}, & \text{if $d=4$; } \frac{d+2+\sqrt[3]{(d-1)d}}{2d+4+\sqrt[3]{(d-1)d}}n<\frac{4n}{7}, & \text{if $d\ge 19$. } \end{cases} \right. \]