Article Contents
Article Contents

# Adjacent vertex distinguishing edge-colorings and total-colorings of the Cartesian product of graphs

• 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 adjacent vertex distinguishing edge-coloring of $G$ if $F_{\sigma}(u)\not= F_{\sigma}(v)$ for any $uv\in E(G)$, where $F_{\sigma}(u)$ denotes the set of colors of edges incident with $u$. A total-coloring $\sigma$ of $G$ is called an adjacent vertex distinguishing total-coloring of $G$ if $S_{\sigma}(u)\not= S_{\sigma}(v)$ for any $uv\in E(G)$, where $S_{\sigma}(u)$ denotes the set of colors of edges incident with $u$ together with the color assigned to $u$. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring (resp. an adjacent vertex distinguishing total-coloring) of $G$ is denoted by $\chi_a^{'}(G)$ (resp. $\chi^{''}_{a}(G)$). In this paper, we provide upper bounds for these parameters of the Cartesian product $G$ □ $H$ of two graphs $G$ and $H$. We also determine exact value of these parameters for the Cartesian product of a bipartite graph and a complete graph or a cycle, the Cartesian product of a complete graph and a cycle, the Cartesian product of two trees and the Cartesian product of regular graphs.
Mathematics Subject Classification: Primary: 05C35, 05C75; Secondary: 05C60.

 Citation:

•  [1] S. Akbari, H. Bidkhori and N. Nosrati, r-Strong edge colorings of graphs, Discrete Math., 306 (2006), 3005-3010.doi: 10.1016/j.disc.2004.12.027. [2] P. N. Balister, E. Győri, J. Lehel and R. H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math., 21 (2007), 237-250.doi: 10.1137/S0895480102414107. [3] J-L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes, Australasian Journal of Combinatorics, 35 (2006), 89-102. [4] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976. [5] M. Chen and X. Guo, Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes, Information Processing Letters, 109 (2009), 599-602.doi: 10.1016/j.ipl.2009.02.006. [6] K. Edwards, M. Horňák and M. Woźniak, On the neighbor-distinguishing index of a graph, Graphs Combin., 22 (2006), 341-350.doi: 10.1007/s00373-006-0671-2. [7] H. Hatami, ∆+300 is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory Ser. B, 95 (2005), 246-256.doi: 10.1016/j.jctb.2005.04.002. [8] S. Tian and P. Chen, On adjacent vertex-distinguishing total coloring of two classes of product graphs, Journal of Mathematical Research and Exposition, 27 (2007), 733-737. [9] H. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with ∆(G)=3, Journal of Combinatorial Optimization, 14 (2007), 87-109.doi: 10.1007/s10878-006-9038-0. [10] H. P. Yap, Total Coloring of Graph, Springer Verlag, New York, 1996. [11] Z. Zhang, X. Chen, J. Li, B. Yao, X. Lu and J. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Science in China Series A, Mathematics, 48 (2005), 289-299.doi: 10.1360/03YS0207. [12] Z. Zhang, L. Liu and J. Wang, Adjacent strong edge coloring of graphs, Applied Mathematics Letters, 15 (2002), 623-626.doi: 10.1016/S0893-9659(02)80015-5.