On the Independence Number of Edge Chromatic Critical Graphs

Abstract

In 1968, Vizing conjectured that for any edge chromatic critical graph $G=(V,E)$ with maximum degree $\mathrm{\Delta }$ and independence number $\alpha (G)$, $\alpha (G)\le \frac{|V|}{2}$. This conjecture is still open. In this paper, we prove that $\alpha (G)\le \frac{3\mathrm{\Delta }-2}{5\mathrm{\Delta }-2}|V|$ for $\mathrm{\Delta }=11,12$ and $\alpha (G)\le \frac{11\mathrm{\Delta }-30}{17\mathrm{\Delta }-30}|V|$ for $13\le \mathrm{\Delta }\le 29$. This improves the known bounds for $\mathrm{\Delta }\in \{11,12,\dots ,29\}$.