Equitable Colorings Of Graphs

Graph Theory has a strong application in modern information science, life sci-ence. Such as:network design, computer science, information science, coding theory, identification and counts of genetic spectrum of DNA.It is widely used graph theory and algorithms in industrial production and the op-timization method of business management. In recent years, four mathematic experts who investigate the area about Graph Theory and Combinatorics were awarded inter-national mathematics prize:JHKim was Awarded Furkerson in 1997; T. Gowers won Fields Prize in 1998; L. Lov'a sz got the Wolf Prize in 1999 and S. Shelah had the Wolf Prize in 2001.Graph coloring is one of the most popular topic in graph theory. As a special case, equitable coloring theory was introduced at an early time in graph coloring problems. It has wide applications in industrial production, business management and biology. Particularly, equitable coloring theory plays an important role in the schedule, split, load balance problems. However, there are less problems were solved on this theory till now. In recent years, with the developing of list coloring problem, people turn to inves-tigate the equitable coloring of graphs. In this thesis, we shall investigate the equitable chromatic number of graphs with special restrictions. it consists three chapters.In Chapter 1, we introduce some definitions and notations used throughout this dissertation and give a chief survey on equitable coloring problems under consideration.In Chapter 2, we discuss the equitable list coloring of planar graphs. Kostochka, Pelsmajer and West introduced 2 conjectures in 2003:Every graph is equitably k-choosable whenever k≥Δ+1; If G is a connected graph withΔ≥3, then G is equi- tably△一choosable unless G is a complete graph or is K2m+1,2m+1.We use discharge rules,proved that every planar graph G is equitably k-choosable and equitably k-col—orable if G has no 4-,8-and 9-cycles and k≥moz{Δ(G),9}；Every planar graph G is equitably k-choosable and equitably k-colorable if G has no 4-,10- cycles and no intersection 5-faces and k≥max{Δ(G),9}.In Chapter 3,we investigate the equitable chromatic number of the total graph and central graph of a spider.By giving the certain independent set,we proved that if graph G was a spider then it contained n paths with the length of n-1 after removing the head. Let T(G)denote the total graph of G,then the equitable chromatic number of the total graph of GχEq[T(G)]=n+1.Let C(G)denote the central graph of G,we also obtain the equitable chromatic number of the central graph of this G:χEq(G)]=2k2+1 when n=2k,χEq[C(G)]=2k2+3k+1 when n=2k+1.