关于临界图性质的一个结论  

A Conclusion on the Properties of Edge-coloring Critical Graphs

作　　者：张岩[1] 苗连英[1] 秦健[1] 苗正科[2] 

机构地区：[1]中国矿业大学理学院,江苏徐州221008 [2]徐州师范大学数学科学学院,江苏徐州221116

出　　处：《徐州师范大学学报（自然科学版）》2007年第3期11-13,共3页Journal of Xuzhou Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(10471037);中国矿业大学科技基金资助项目(OZK4566)

摘　　要：图的边色数是指对图的边进行染色使得任意两相邻边染不同的颜色所需要的最少的色数.1965年,Vizing证明了任意最大度是Δ的图的边色数或者是Δ或者是Δ+1.若为前者,则称图是第一类的,否则称为第二类的.若G为连通的第二类图,且对G的任意边e,有χ′(G-e)<χ′(G),则称图G为Δ临界图.对于临界图的性质的研究有助于对图的分类问题的研究.本文给出了如下定理:G是一个Δ临界图,x是G中的一个Δ点,如果|N4(x)|=3,那么对u∈N4(x),N≤Δ-1(u)=φ.The chromatic index Х＇（G） of a graph G is the minimum number of colors required to color the edges of G so that two adjacent edges receive different colors. In 1965,Vizing proved that if G is a graph of maximum degree △, then Х＇（G） is either △ or △＋1. A graph G is said to be of class one if Х＇（G）=△, and it is said to be of class two if Х＇（G）=△＋1. A △ critical graph G is a connected graph of maximum degree △ such that G is of class two and G-e is of class one for each edge e of G. In this paper, the theorem is given that let G be a △ critical graph, x∈V（G） and d（x） =△,if │N4（x）│ = 3, then for any u∈N4 （x）,N≤△-1（u）=φ.

关 键 词：边染色 边色数 临界图 

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