A Conclusion on the Properties of Edge-coloring Critical Graphs
Zhengke Miao · Journal of Xuzhou Normal University · 2007
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)=φ.