A New Upper Bound for the Independence Number of Edge Chromatic Critical Graphs
Abbreviated Journal Title
J. Graph Theory
edge coloring; independence number; critical graphs; CONJECTURE; Mathematics
In 1968, Vizing conjectured that if G is a Delta-critical graph with n vertices, then alpha(G) < = n/2, where alpha(G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that alpha(G) < (((5 Delta-6)n)/(8 Delta-6)) < 5n/8 if Delta > = 6. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202-212, 2011
Journal of Graph Theory
"A New Upper Bound for the Independence Number of Edge Chromatic Critical Graphs" (2011). Faculty Bibliography 2010s. 1603.