临界图独立数的上界

On the upper bound of the independence number of edge chromatic critical graphs

1968年,Vizing猜想,对于n阶的Δ临界图G,其独立数α(G)≤2n.利用著名的Vizing邻接引理和Fiorini不等式的证明方法,证明了如果临界图G的一个最大独立集中主顶点个数不超过1,则猜想成立,从而改进了Luo等的一个结果.

In 1968, Vizing conjectured that for any edge chromatic critical graph G of order n with maximum degree △, its independence number a（G）≤n/2. In this paper, by using Vizing adjacency lemma and the method in the proof of Fiorini inequality, it is proved that if in some maxmal independent set of G the number of major vertices is no more than one, then the conjecture is true.