| This article investigates the adjacent vertex-distinguishing edge coloring and the adjacent vertex-distinguishing total coloring of the generalized lexicographic product of graphs, the vertex-distinguishing edge coloring and the adjacent vertex-distinguish-ing total coloring of the semistrong product. The upper bounds of the corresponding chromatic numbers were provided using the method of graph decomposition and tectonic coloring, and these were proved to be attainable precisely. On the basis, the exact values of the corresponding chromatic numbers of the generalized lexicogra-phic product and the semistrong product of some special graphs were determined. The main results include four parts:First, for the generalized lexicographic product G[hn] of a graph G and a sequence of graphs hp=(Hi)i∈{0,1...,n-1},two upper bounds of the adjacent vertex-dis-tinguishing edge chromatic numbers are obtained:(1) if G has a χ’as(G)-adjacent vertex-distinguishing edge coloring, all maximum degrees of G are all saturated with the edges of one color class of the coloring, then χ’as(G[hn])≤mχ’as(G)+χ’(H0)+1, where χ’(H0)=max{χ’(Hi)|ti∈V△(G)},V△(G) is a set of all maximum degrees of G.(2) χ’as(G[hn])≤mχ’as(G)+χ’(H0),where χ’as(H0)=max{χ’as(Hi)|ti∈V△(G)}.The two upper bounds were proved to be attainable precisely. For any graph G with χ’as(G)=△(G), the exact values of the adjacent vertex-distinguishing edge chromatic numbers of G[hn] are provided, where Ho is a complete graph and a tree respectively. For the lexicographic product G[H] and H[G] of a graph G and H with χ’as(G)=△(G) and χ’as(H)=△(H), the adjacent vertex-distinguishing edge chromatic numbers are provided. In addition, for p connected graphs which have the same maximum degree and the adjacent vertex-distinguishing edge chromatic number is the maximum degree, the adjacent vertex-distinguishing edge chromatic number of Gp[Gp-1[…G2[G1]…]] is provided, and it is proved that the chromatic number has nothing to do with the order of G1,G2,...,Gp.Second, for the wheel or fan or star with n≥ 6 order and a connected sequence of graphs hp=(Hi)i∈{0,1...,n-1} with m≥2 order, an upper bound of the adjacent vertex-distinguishing total chromatic number of G[hn] is provided and it is proved to be attainable precisely: χ’at(G[hi])≤m(m-1)+min{χr(H0)+1,χat,(H0)}, where Ho is corresponding t0 which is the maximum degree of G. The exact values of the adjacent vertex-distinguishing total chromatic numbers of G[hn] were obtained using the results, when Ho is a tree, cycle, path, complete graph and regular bipartite graph respectively.Third, for the semistrong product G·H of two simple and connected graphs G and H, both of them with 3 order at least, an upper bound of the vertex-distingui-shing edge chromatic number is obtained and it is proved to be attainable precisely: χ’vd(G·H)≤△(H)χ’vd(G)+χ’vd(H). On this basis, for G with χ’vd(G)=△(G), the exact values of the vertex-distinguishing edge chromatic numbers of the semistrong product of G and H with χ’vd(H)=△(H), G and a complete graph are provided. In addition, for p connected graphs which have the same maximum degree and the vertex-distinguishing edge chromatic number is the maximum degree, the vertex-distinguishing edge chromatic number of Gp·(Gp-1·(…·(G2·G1)…)) is provided, and it is proved that the chromatic number has nothing to do with the order of G1,G2,...,Gp.Forth, for G·H, of two simple and connected graphs G and H, both of them with 2 order at least, an upper bound of the adjacent vertex-distinguishing total chromatic number is obtained and it is proved to be attainable precisely: χ’vd(G·H)≤△(H)χ’vd(G)+χ’vd(H). For the semistrong products of the first class graph and a nontrivial tree or cycle, two regular bipartite graphs and two nontrivial trees, the adjacent vertex-distinguishing total chromatic numbers are obtained using the upper bound. In addition, for Tp-1·(Tp-2·(...·(T1·T0)...)), the semistrong product of p nontrivial trees, the adjacent vertex-distinguishing total chromatic number is provided. |
