Independence number of edge‐chromatic critical graphs.

Let G $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 graph G $G$ is called edge‐Δ ${\rm{\Delta }}$‐critical if G $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 every e∈E(G) $e\in E(G)$. Let G $G$ be an n $n$‐vertex edge‐Δ ${\rm{\Delta }}$‐critical graph. Vizing conjectured that α(G) $\alpha (G)$, the independence number of G $G$, is at most n2 $\frac{n}{2}$. The current best result on this conjecture, shown by Woodall, is α(G)<3n5 $\alpha (G)\lt \frac{3n}{5}$. We show that for any given ε∈(0,1) $\varepsilon \in (0,1)$, there exist positive constants d0(ε) ${d}_{0}(\varepsilon)$ and D0(ε) ${D}_{0}(\varepsilon)$ such that if G $G$ is an n $n$‐vertex edge‐Δ ${\rm{\Delta }}$‐critical graph with minimum degree at least d0 ${d}_{0}$ and maximum degree at least D0 ${D}_{0}$, then α(G)<12+εn $\alpha (G)\lt \left(\frac{1}{2}+\varepsilon \right)n$. In particular, we show that if G $G$ is an n $n$‐vertex edge‐Δ ${\rm{\Delta }}$‐critical graph with minimum degree at least d $d$ and Δ(G)≥(d+1)4.5d+11.5 ${\rm{\Delta }}(G)\ge {(d+1)}^{4.5d+11.5}$, then α(G)<7n12ifd=3,4n7ifd=4,d+2+(d−1)d32d+4+(d−1)d3n<4n7ifd≥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.$ [ABSTRACT FROM AUTHOR]