The Acyclic Vertices(Total)Coloring And Distance Coloring Of The Product Graphs Of Paths

An k-acyclic vertex coloring of a graph G is a k-proper vertex coloring of G such that the union of any two color classes induces a subgraph of G which is a forest.The acyclic chromatic index of G,denoted by a(G)is the least number of colors in an acyclic vertex coloring of G.An k-acyclic total coloring of a graph G is a k-proper total coloring of G,such that there are at least 4 colors on those vertices and edges incident with a cycle of G.The acyclic total chromatic number of G,denoted by a_T(G),It is the least number of colors in an acyclic total coloring of G.A d-distance coloring of a graph G with k colors is a k-proper vertex coloring of G such that two vertices lying at distance less than or equal to d must be assigned different colors.The d-distance chromatic number of G,denoted by x_d(G),is the least number of colors in a d-distance coloring of G.The acyclic vertex coloring,acyclic total coloring and d-distance coloring of Cartesian product,direct product,semi-strong product,strong product and lexicographic product of paths are studied in this paper,and the corresponding chromatic number are obtained using method of constructing the coloring and contradiction.The main contents include the following three parts.Firstly,The acyclic vertex chromatic number of some produts of two paths P_m and P_n are obtained,such as the direct product,semi-strong product,strong product P_m(?)P_n.In addition,the acyclic vertex chromatic number of lexicographic product P_m[H]is given,where H is a simple graph of order n and n,m ≥ 2.Secondly,The acyclic total chromatic number of some produts of two paths P_m and P_n are given,such as the Cartesian product,direct product,semi-strong product,strong product,where n,m≥ 2.Finally,The d-distance chromatic number of the lexicographic product path P_m and a simple graph H of order n is given.