A note on Vizing's independence number conjecture of edge chromatic critical graphs (Q2502907)

A graph \(G=(V,E)\) is said to be critical if it is connected, its chromatic index \(\chi^\prime(G)\) is equal to \(\Delta(G)\) and \(\chi^\prime(G-e)<\chi^\prime(G)\) for every edge \(e\in E\). A critical graph \(G\) of maximum degree \(\Delta\) is called \(\Delta\)-critical graph. \textit{V. G. Vizing} [Russ. Math. Surv. 23, No.~6, 125--141 (1968; Zbl 0192.60502); translation from Usp. Mat. Nauk 23, No.~6, 117-134 (1968)] conjectured that if \(G\) is a \(\Delta\)-critical graph with \(n\) vertices then \(\alpha(G)\leq n/2\), where \(\alpha(G)\) is the independence number of \(G\). The authors verify the conjecture for the graphs with \(n\leq 2\Delta\).