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

A RESULT ON THE NUMBER OF MAJOR VERTEX OF CRITICAL GRAPHS

作　　者：田大东[1] 张埂[2] 李梅[1] 

机构地区：[1]青岛理工大学临沂校区基础课教学部,山东费县273400 [2]四川文理学院,,四川达州635000

出　　处：《山东师范大学学报（自然科学版）》2013年第4期7-9,共3页Journal of Shandong Normal University(Natural Science)

摘　　要：如果一个连通的第二类图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.

关 键 词：临界图 边染色 第一类图 第二类图 

分 类 号：O157.5[理学—数学]