科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
- 出版日期2011-11
