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 \(\Delta\) and independence number \(\alpha(G)\), \(\alpha(G) \leq \frac{|V|}{2}\). This conjecture is still open. In this paper, we prove that \(\alpha(G) \leq \frac{3\Delta-2}{5\Delta-2}|V|\) for \(\Delta = 11, 12\) and \(\alpha(G) \leq \frac{11\Delta-30}{17\Delta-30}|V|\) for \(13 \leq \Delta \leq 29\). This improves the known bounds for \(\Delta \in \{11, 12, \ldots, 29\}\).