Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs

Abstract

‎Let $G$ be a graph and $chi^{prime}_{aa}(G)$ denotes the minimum number of colors required for an‎ ‎acyclic edge coloring of $G$ in which no two adjacent vertices are incident to edges colored with the same set of colors‎. ‎We prove a general bound for $chi^{prime}_{aa}(Gsquare H)$ for any two graphs $G$ and $H$‎. ‎We also determine‎ ‎exact value of this parameter for the Cartesian product of two paths‎, ‎Cartesian product of a path and a cycle‎, ‎Cartesian product of two trees‎, ‎hypercubes‎. ‎We show that $chi^{prime}_{aa}(C_msquare C_n)$ is at most $6$ fo every $mgeq 3$ and $ngeq 3$‎. ‎Moreover in some cases we find the exact value of $chi^{prime}_{aa}(C_msquare C_n)$‎.

Keywords

• ‎Acyclic edge coloring‎
• ‎adjacent vertex distinguishing acyclic edge coloring‎
• ‎adjacent vertex distinguishing acyclic edge chromatic number