边染色临界图主顶点数的一个结果

A RESULT ON THE NUMBER OF MAJOR VERTEX OF CRITICAL GRAPHS

如果一个连通的第二类图G去掉任意一条边后其边色数都比图G小,则称它是一个临界图.最大顶点度为△的临界图称作△-临界图.1968年,Vizing猜想任意n阶△-临界图G边数m的下界为（nΔ-n＋3）/2.Fiorini不等式和差值转移法被广泛用于研究此猜想.笔者利用Vizing邻接引理和临界图的结构性质给出了Δ-临界图在△≥6且（Δ-1）度顶点至多邻接一个四度顶点时Fiorini不等式的一个新的下界.

Let G be a connected graph that is also class two,for any edge e of G,if the edge chromatic number of G／e is strictly less than G,then G is a critical graph.We call a graph is Δ-critical if it is a critical graph with maximum degree Δ.In 1968,Vizing conjectured that the size of a Δ-critical graph of order n is no less than（nΔ-n ＋ 3）/2.Fiorini inequality and discharging method are widely used to prove the above conjecture.By using Vizing Adjacency Lemma and some properties of critical graph,we give a new lower bound to Fiorini inequality for Δ-critical graph when Δ≥6 and every（Δ-1）-vertex in G is adjacent at most one 4-vertex.