Mousavi, F., Noori, M. (2017). Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs. Transactions on Combinatorics, 6(2), 19-30. doi: 10.22108/toc.2017.20988

Fatemeh Sadat Mousavi; Massomeh Noori. "Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs". Transactions on Combinatorics, 6, 2, 2017, 19-30. doi: 10.22108/toc.2017.20988

Mousavi, F., Noori, M. (2017). 'Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs', Transactions on Combinatorics, 6(2), pp. 19-30. doi: 10.22108/toc.2017.20988

Mousavi, F., Noori, M. Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs. Transactions on Combinatorics, 2017; 6(2): 19-30. doi: 10.22108/toc.2017.20988

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

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}(G\square 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_m\square C_n)$ is at most $6$ fo every $m\geq 3$ and $n\geq 3$. Moreover in some cases we find the exact value of $\chi^{\prime}_{aa}(C_m\square C_n)$.

[1] D. Amar, A. Raspaud and O. Togni, All-to-all wavwlength-routing in all-optical comp ound networks, Discrete Math., 235 (2001) 353-363.

[2] P. N. Balister, E. Gyori, J. Lehel and R. H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math., 21 (2007) 237-250.

[3] J. L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes, Australas. J. Combin., 35 (2006) 89-102.

[4] X. S. Liu, M. Q. An and Y. Gao, An upp er b ound for the adjacent vertex distinguishing acyclic edge chromatic numb er of a graph, Acta Math. Appl. Sin. Engl. Ser., 25 (2009) 137-140.

[5] W. C. Shiu, W. H. Chan, Z. F. Zhang and L. Bian, On the adjacent vertex-distinguishing acyclic edge coloring of some graphs, Appl. Math. J. Chinese Univ. Ser. B., 26 (2011) 439-452.

[6] J. J. Sylverster, Mathematical questions with their solutions, in: the Educational Times, 41, Francis Ho dgson, London, 1884 171-178.

[7] S. Tian, P. Chen, Y. Shao and Q. Wang, Adjacent vertex distinguishing edge-colorings and total colorings of the Cartesian pro duct of graphs, Numer. Algebra Control Optim., 4 (2014) 49-58.

[8] Z. F. Zhang, L. Z. Liu and J. F. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett., 15 (2002) 623-626.