Equitable Colorings Of Graphs

The coloring of graphs, one of the most interesting and rapidly growing areas of researches in graph theory, has great theoretical value and applied background. Equitable coloring of graphs extends the theory about coloring graphs. A great number of problems about the equitable coloring theory are unsolved so far. This dissertation mainly discusses the equitable coloring of graphs.This thesis consists of four chapters. Chapter 1 is an introduction to the background of the research presented in the thesis.Chapter 2 deals with the equitable coloring of graphs. The purpose is to confirm THE EQUITABLE △-COLORING CONJECTURE for some graphs. We mainly study the plane graphs. We verify this conjecture for a plane graph without i-cycles, 3 ≤ i ≤ 5, or a plane graph without 4-cycles(or 5-cycles) and 6-cycles.Chapter 3 is devoted to equitable list coloring of graphs. Kostochka Pelsmajer and West conjectured that for k ≥ △(G), every graph G is equitably k-choosable. We apply the results in Chapter 2 to the equitable list coloring of graphs and prove that a graph G is equitably △(G)-choosable if G is a plane graph without i-cycles, 3 ≤ i ≤ 5, or a plane graph without 4-cycles(or 5-cycles) and 6-cycles.In Chapter 4, we calculate the equitable total chromatic number of some specific graphs. For some plane graph, we also calculate the vertex-edge-face equitable total chromatic number.