A new upper bound for the independence number of edge chromatic critical graphs
Rong Luo, Yue Zhao · Journal of Graph Theory · 2010
In 1968, Vizing conjectured that if G is a Δ-critical graph with n vertices, then α(G)≤n/2, where α(G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that α(G)<(((5Δ−6)n)/(8Δ−6))<5n/8 if Δ≥6. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202-212, 2011