Seeing The Equitable Colorings In A Different View

Graph Theory is a branch of mathematics. These graphs are studied in graph theory. Many real-world situations can conveniently be described by means of a diagram consisting of a set of points together with lines joining certain pairs of these points.Since 1960s, graph theory has developed very fast and numerous results on graph theory sprung forth. There are many nice and well-known problems in graph theory, such as Hamiltonian problem, four-color problem, Chinese postman problem, etc. Moreover, graph theory is widely applied in chemistry, computer science, biology and other disciplines. As a subfield in discrete mathematics, graph theory has attracted much attention from all perspectives.Equitable coloring problem is an important problem in graph, which has some far-reaching significance. A proper vertex coloring of a graph is equitable if the sizes of its color classes differ by at most one. All graphs considered in this paper are finite, loopless, and without multiple edges.This paper shows some problems in graph theory. Specifically, we start from the equitable coloring on tree, add some edges to the tree, which forms the new graph with some circles, and then do some classifications, which is so easier to find the equitable colorings of the graph.This paper is divided into five chapters.In chapter 1, we give a briefly and relatively complete introduction. Firstly, we give some basic terms and definitions. Then, we introduce the theory of equitable coloring. Finally, we list the main results.In chapter 2, we study the equitable coloring on tree.In chapter 3, we study the other simple graphs which are connected. We will approach the problem from three cases. In case 1, we suppose that there are no odd cycles in the graph G, i.e. it is a bipartite graph. In case 2, we suppose that there are no even cycles. And there is no co-edge and co-vertex ideally. Obviously, any two cycles don't intersect in the graph G. The main sub-cases can be summarized as follow:1) Suppose there are no sub-trees of‖X‖-‖Y‖≥2. Suppose there are some sub-trees Ti of‖X|-|Y‖≥2.We choose the maximum equitable coloring of these sub-trees Ti, where we define Ti is the one whose equitable coloring is the maximum. Then we suppose Ti is equitably k1-colorable, where k1≥3.It is clear that G is at most equitably A:,-colorable.So we can probe the critical value k from 3 to k1 using binary search method. In case 3, suppose there are some co-edge or co-vertex. The problem becomes even more complicated. However, we can use a tree decomposition of the graph G to find the treewidth w of it (i.e. w-degenerate), and then the following theorem can help us to probe the k which can make the graph G equitablyκ:-colorable.In chapter 4, we study the equitable coloring on forests. For other cases, we can find equitable chromatic numberχ=(G) from the Part 3. And then, to the graph G, obviously, it can be equitably maxχ=(Gi)-colorable. However, you know, the graph G don't have the impossibility to be equitably k1-1-colorable.In chapter 5, we consider some extensions of the equitable coloring.