There Is Uniform Staining Of The Limitations Of The Plan

Let G be a graph,a vertex coloring of G is an assignment of k colors 1,2,..,k to the vertices of G such that no adjacent vertices have the same color. let V² denote the set of vertices colored i. We call a vertex coloring of a graph G an equitble k-coloring if ||Vⁱ| - |V^j|| ≤ 1 for all i and j. The smallest integer k for which G has an equitable k-coloring is defined to be the equitable chromatic number of G, denoted by Xe(G).Meyer^[1] proved that any tree T has an equitable ([△(T/2)] + l)-coloring and he made the following conjecture:Conjecture 1 For any connected graph G, except K_m and C_2m+1 for all m ≥ l,Xe(G) ≤ △(G).Hajnal and Szemeredi proved that every graph G has an equitable k-coloring for any k ≥ △(G) + 1. Y.Zhang and H.P.Yap proved that the planar graph with maximum degree △ ≥ 13 is equitably m—colorable for any m ≥△.Lih and Wu (Yap[12]) proved that a connected bipartite graph G has an equitable △-coloring if G is different from the complete bipartite graph K_2m+1,2m+1 for all m ≥0 . Basis on this result, Chen, Lih and Wu put forth the following conjecture:Conjecture 2 For any connected graph G, except K_m, C_2m+1 and K_2m+1,2m+1 for all m ≥ 0,then G is equitably △—colorable .In [7], Yap and Zhang proved that conjecture 2 is true for outerplanar graphs G with A ≥ 3;and In [9],proved that conjecture 2 is true for graphs G satifying △(G) > |G|/3 + 1.In this paper we first give some background and knowledge about equitable coloring. In the second ,the third and the fourth chapters,we discuss three questions in detail respectively:1. For any planar graph G of order n ,if g ≥ 4,then e ≤ 2n — 4 and δ ≤ 3 ;...