Equitable Colorings Of Graphs

This dissertation is devoted to study the equitable coloring problems and it consists of four chapters.In Chapter 1,we introduce some definitions and notations used through-out this dissertation and give a chief survey on equitable coloring problems under consideration.In Chapter 2,we discuss the equitably list colorings of planar graphs. In 2003,Kostochka,Pelsmajer and West introduced 2 conjectures.One states that every graph G is equitably k-choosable whenever k≥A(G)+ 1 and another states that if G is a connected graph with maximum degree△≥3,then G is equitably△-choosable unless G is a complete graph or is K_2m+1,2m+1.We prove that G satisfies these two conjectures if G is a triangle-free planar graphs with maximum degree at least 8 or G is a planar graphs with maximum degree at least 7 and without 4-cycles and 5-cycles, or G is a planar graphs with maximum degree at least 8 and without 4-cycles and 7-cycles.Furthermore,we show that these two conjectures hold for outerplane graphs.In Chapter 3,we investigate the equitably colorings of planar graphs. In 1973,Meyer introduced the notion of equitable coloring and conjec-tured that the equitable chromatic number of a connected graph G,which is neither a complete graph nor odd cycle,is at most△(G).In 1994,B.-L.Chen,K.-W.Lih and R-L.Wu put forth the conjecture that a connected graph G is equitably△(G)-colorable if it is different from K_m,C_2m+1and K_2m+1,2m+1for m≥1.We apply the results in Chapter 2 to the equitable colorings of planar graphs and prove that G satisfies these two conjectures if G is a triangle-free planar graphs with maximum degree at least 8 or G is a planar graphs with maximum degree at least 7 and without 4-cycles and 5-cycles,or G is a planar graphs with maximum degree at least 8 and without 4-cycles and 7-cycles.Chapter 4 is devoted to calculate the equitable total chromatic number of join graph P_n∨K_m,n.In 2002,Wang Weifan conjectured thatχ_et(G)≤△(G)+ 2 holds for any graph G.We prove this conjecture holds for join graph P_n∨K_m,nfurthermore,we prove thatχ_et(P_n∨K_m,n)=△(P_n∨K_m,n)+ 1 when m≠n - 2.