A new upper bound for the independence n
β
Rong Luo; Yue Zhao
π
Article
π
2010
π
John Wiley and Sons
π
English
β 107 KB
π 2 views
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