Adjacent Strong Edge Chromatic Number And Adjacent Vertex Distinguishing Total Chromatic Number Of Two Classes Of Operator Graphs

The concepts of adjacent strong edge coloring and adjacent vertex distinguishingtotal coloring were introduced by Zhang Zhong-fu et al in 2002 and 2004, respectively.The adjacent strong edge coloring of graph G is a proper edge coloring in which anytwo adjacent vertices have different color sets, the minimum number of colors required iscalled adjacent strong edge chromatic number, which is denoted by X'_as(G); The adjacentvertex distinguishing total coloring of graph G is a proper total coloring in which any twoadjacent vertices have different color sets, the minimum number of colors required is calledadjacent vertex distinguishing total chromatic number, which is denoted by X_at(G).The adjacent strong edge coloring and adjacent vertex distinguishing total coloringfor some special graphs were studied in references [1] and [2]. Based on those concepts aconjecture about chromatic number comes: Let G be a connected graph with |V(G)|≥3,and G≠C₅. Then X'_as(G)≤Δ(G)+2; Let G be a simple connected graph with |V(G)|≥2. Then X_at(G)≤Δ(G)+3.By the means of graph decomposition, the adjacent strong edge coloring and adjacentvertex distinguishing total coloring are constructed for a certain kind of balanced multiplejoin graphs K(r, 2m) (balanced complete r-partition graph in which every partitionhas 2m vertices), the following result can be obtained: if r≥3, then X'_as(K(r, 2m))=2m(r-1)+1; if r≥2, then X_at(K(r, 2m))=2m(r-1)+2. Following these, we getsome further results: Let H be a graph of orders 2m. If X'_as(H)=Δ(H) and r≥3, thenX'_as(K(r, H))=2m(r-1)+Δ(H)+1; Let H be a bipartite graph having bipartition(X, Y), when |X|=2s and |Y|=2t, where s,t≥1. If r≥2, then X_at(K(r, H))=2(s+t)(r-1)+Δ(H)+2. Secondly, some relative results about the adjacent strong edge coloring and adjacentvertex distinguishing total coloring for product of a path and a complete graph are obtainedin reference [3] and [4]. Using the methods of substituting colors set and so on, wegeneralize the above results to the product of a bipartite graph G and a complete graphK_n, the following result can be obtained: if n≥3, then the adjacent strong edge chromaticnumber equalsΔ(G)+n; if n≥2, then the adjacent vertex distinguishing total chromaticnumber equalsΔ(G)+n+1. In addition, the adjacent strong edge chromatic number andthe adjacent vertex distinguishing total chromatic number are studied on a certain classof products, such as, the product of a bipartite graph with a circle, the product of twotrees. After these, some upper bounds about adjacent strong edge chromatic number andthe adjacent vertex distinguishing total chromatic number of some special product graphs,are given.Finally, the followed conclusions are drawn about the conjecture of adjacent strongedge chromatic number and the adjacent vertex distinguishing total chromatic number:the product of a bipartite graph G and a graph H which satisfies the conjecture thatthe adjacent strong edge chromatic number (or the adjacent vertex distinguishing totalchromatic number) also conforms with the conjecture of adjacent strong edge chromaticnumber (or the adjacent vertex distinguishing total chromatic number).