Equitable Colorings Of Cartesian Products Graphs

Graph colorings theory has the most important role in discrete mathematics,espe-cially the equitable colorings,having been widely applied in various fields.Over the past few decades,the problems of equitable colorings get more and more attention.A graph is k-colorable if it has a proper k-coloring.The chromatic number of G is χ(G)=min {k:G is k-colorable}.A graph G is said to be equitably k-colorable if the vertex set of G can be divided into k independent sets for which any two sets differ in size at most one.The equitable chromatic number of G,x=(G),is the minimum k for which G is equitably k-colorable.The equitable chromatic threshold of G,χ*=(G),is the minimum k for which G is equitably k’-colorable for all k’≥k.The concept of equitable colorability was first introduced by Meyer[20].In 1957,Sabidussi gives the following results.Theroem 1([21])If G and H are graphs,then χ(G□H)=max{χ(G),χ(H)}.It is clear from the definition that χ(G)≤X=(G)≤χ*=(G)for any graph G.Lin and Chang believed that it was possible to bound χ=(G□H)by usual colorability of its factors and raised the following conjecture at the end of[19].Conjecture 1([19])χ=(G□H)≤χ(G)χ(H)for any connected graphs G and H.This paper mainly consists of three chapters:In chapter one,we introduce some preliminaries,the necessary symbols and the relative studying background of the equitable colorings.In chapter two,we get the exact values of χ*=(G□H)and χ=(G□H)when G is the square of a cycle or a path and H is a complete bipartite graph.In chapter three,we get the exact values of χ*=(Pn’,2□Km,n)and ×=(Pn’,2□Km,n)except that 3≤χ*=(P5,2□Km,n)=χ＝(P5,2□Km,n)≤4 when m+n>3min {m,n}+2 or m+n<3min{m,n}-2.By the results above,we obtain that Conjecture 1 holds for two Cartesian products graphs that we research in the paper.