Independence number of edge‐chromatic critical graphs

LetG $G$ be a simple graph with maximum degreeΔ ( G )${\rm{\Delta }}(G)$ and chromatic indexχ ′ ( G )$\chi ^{\prime} (G)$ . A classical result of Vizing shows that eitherχ ′ ( G ) = Δ ( G )$\chi ^{\prime} (G)={\rm{\Delta }}(G)$ orχ ′ ( G ) = Δ ( G ) + 1 $\chi ^{\prime} (G)={\rm{\Delta }}(G)+1$ . A simple graphG $G$ is called edge‐ Δ ${\rm{\Delta }}$ ‐critical ifG $G$ is connected,χ ′ ( G ) = Δ ( G ) + 1 $\chi ^{\prime} (G)={\rm{\Delta }}(G)+1$ andχ ′ ( G − e ) = Δ ( G )$\chi ^{\prime} (G-e)={\rm{\Delta }}(G)$ for everye ∈ E ( G )$e\in E(G)$ . LetG $G$ be ann $n$ ‐vertex edge‐ Δ ${\rm{\Delta }}$ ‐critical graph. Vizing conjectured thatα ( G )$\alpha (G)$ , the independence number ofG $G$ , is at mostn 2$\frac{n}{2}$ . The current best result on this conjecture, shown by Woodall, isα ( G ) < 3 n 5$\alpha (G)\lt \frac{3n}{5}$ . We show that for any givenε ∈ ( 0 , 1 )$\varepsilon \in (0,1)$ , there exist positive constantsd 0 ( ε )${d}_{0}(\varepsilon )$ andD 0 ( ε )${D}_{0}(\varepsilon )$ such that ifG $G$ is ann $n$ ‐vertex edge‐ Δ ${\rm{\Delta }}$ ‐critical graph with minimum degree at leastd 0${d}_{0}$ and maximum degree at leastD 0${D}_{0}$ , thenα ( G ) <1 2 + ε n $\alpha (G)\lt \left(\frac{1}{2}+\varepsilon \right)n$ . In particular, we show that ifG $G$ is ann $n$ ‐vertex edge‐ Δ ${\rm{\Delta }}$ ‐critical graph with minimum degree at leastd $d$ andΔ ( G ) ≥ ( d + 1 ) 4.5 d + 11.5${\rm{\Delta }}(G)\ge {(d+1)}^{4.5d+11.5}$ , thenα ( G ) <7 n 12ifd = 3 ,4 n 7ifd = 4 ,d + 2 +( d − 1 ) d 32 d + 4 +( d − 1 ) d 3n < 4 n 7ifd ≥ 19 .$\alpha (G)\lt \left.\left\{\displaystyle \begin{array}{cc}\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\lt \frac{4n}{7} & \,\text{if}\,\,d\ge 19.\end{array}\right.$