Research On Chromatic Index Critical Graphs With Six Major Vertices

Edge coloring of a graph G is to color the edges of G.A proper edge coloring of G satisfies no two adjacent edges of G receive the same colors.The chromatic index is the minimum number of all possible proper edge colorings of G.Since a vertex having maximum degree is incident withâ–³edges which requireâ–³colors,the chromatic index of G is more than the maximum degree of G.The fundamental theorem of edge coloring,made by Vizing in 1964,claims that the chromatic index of arbitrary simple graph G is equal toâ–³(G)orâ–³(G)+1.If the chromatic index of G is equal toâ–³(G),then G is said to be of class 1,otherwise G is said to be of class 2.Then Vizing introduced the terminology of critical graphs,to study the classification of class 1 graphs and class 2 graphs.A graph G is said to be chromatic index critical if G is connected,of class 2, and the chromatic index of G-e less than that of G's,for any edge e of G.The research on chromatic index critical graph is important to edge coloring.The sizes of chromatic index critical graphs are the least of class 2 graphs.So far,A.G.Chetwynd and A.J.W. Hilton showed the necessary and sufficient conditions of a simple graph with three major vertices is of class 2.Then they proved that any chromatic index critical graph of even order with four major vertices does not exist,and the size of chromatic index graph of odd order with four major vertices is presented.H.P.Yap and Zi-Xia Song also proved any chromatic index critical graph of even order with five major vertices does not exist.Then the size of chromatic index graph of odd order with five major vertices is fixed by Zi-Xia Song.In this paper,we discuss the chromatic index graphs with six major vertices.In section 1, we introduce some concepts and theorems of chromatic index critical graphs.In section 2,first, we show that if chromatic index critical graph G of even order with six major vertices exists, then G has a perfect matching.Then we prove that chromatic index critical graph of even order with six major vertices does not exist.In section 3,we research on the chromatic index critical graph of odd order with six major vertices,and get some simple properties about them.