Adjacent vertex distinguishing edge-colorings and total-colorings of the Cartesian product of graphs
Shuangliang Tian, Ping Chen, Yabin Shao, Qian Wang · Numerical Algebra Control and Optimization · 2013
Let $G$ be a simple graph with vertex set $V(G)$ and edge set$E(G)$. An edge-coloring $\sigma$ of $G$ is called an adjacentvertex distinguishing edge-coloring of $G$ if $F_{\sigma}(u) ot=F_{\sigma}(v)$ for any $uv\in E(G)$, where $F_{\sigma}(u)$ denotesthe set of colors of edges incident with $u$. A total-coloring$\sigma$ of $G$ is called an adjacent vertex distinguishingtotal-coloring of $G$ if $S_{\sigma}(u) ot= S_{\sigma}(v)$ for any$uv\in E(G)$, where $S_{\sigma}(u)$ denotes the set of colors ofedges incident with $u$ together with the color assigned to $u$. Theminimum number of colors required for an adjacent vertexdistinguishing edge-coloring (resp. an adjacent vertexdistinguishing total-coloring) of $G$ is denoted by $\chi_a^{'}(G)$(resp. $\chi^{''}_{a}(G)$). In this paper, we provide upper boundsfor these parameters of the Cartesian product $G$ □ $H$ of twographs $G$ and $H$. We also determine exact value of theseparameters for the Cartesian product of a bipartite graph and acomplete graph or a cycle, the Cartesian product of a completegraph and a cycle, the Cartesian product of two trees and theCartesian product of regular graphs.