Contraction Graph Method For The Interval Edge-Colorings Of Graphs

Graph theory as a branch of mathematics,has developed rapidly and used widely,has been widely used in operations research,cybernetics,information theory and computer science and other fields.Generally speaking,the graph coloring problem originated from the famous”Four-colour Problem”.Due to the coloring problem of graph reflects the extensive and profound practical background,its research lead to the development of the entire graph.Now graph coloring theory is widely used in chemical storage,test schedule and arrange meetings and many other practical problems.An edge-coloring of a graph G with colors 1,2,...,t is an interval t-coloring if all colors are used,and the colors of edges incident to each vertex of G are distinct and form an interval of integer.A graph G is interval colorable if it has an interval t-coloring for some positive integer t.The set of all interval colorable graphs is denoted by N.For a graph G ∈ N,the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G)and W(G),respectively.In this paper,we introduce a contraction graph method for the interval edge-colorings of graphs.By using this method,we show that w(G)= ?(G)or ?(G)+ 1 for any bicyclic graph G ∈ N.Moreover,we completely determine bicyclic graphs with w(G)= ?(G)and w(G)= ?(G)+ 1,respectively.This paper is organized as follows.In Chapter 1,we first introduce some research background and applications of graph coloring and the problem of characterizing interval edge-coloring.Next we introduce some useful definitions and symbols.At last we list some known results about the interval edge-coloring of graphs.In Chapter 2,we introduce a contraction graph method for the interval edge-colorings of graphs.In Chapter 3 we mainly use the methods we have obtained to characterize the lower bounds for the interval edge-coloring of bicyclic graphs.Chapter 3contains there sections.In the first section,we give the lower bounds w(G)for the interval edge-coloring of bicyclic graphs G ∈ B∞.In the sencond section,we give the lower bounds w(G)for the interval edge-coloring of bicyclic graphs G ∈ Bθ.In the last section,we give the lower bounds w(G)for the interval edge-coloring of bicyclic graphs G ∈ B??.