PDF
Discussiones Mathematicae Graph Theory 31(3) (2011)
547-557
DOI: https://doi.org/10.7151/dmgt.1564
ADJACENT VERTEX DISTINGUISHING EDGE COLORINGS OF THE DIRECT PRODUCT OF A REGULAR GRAPH BY A PATH OR A CYCLE
| Laura Frigerio
Dip. di Elettronica e Informazione | Federico Lastaria and Norma Zagaglia Salvi
Dip. di Matematica |
Abstract
In this paper we investigate the minimum number of colors required for a proper edge coloring of a finite, undirected, regular graph G in which no two adjacent vertices are incident to edges colored with the same set of colors. In particular, we study this parameter in relation to the direct product of G by a path or a cycle.Keywords: chromatic index, adjacent vertex distinguishing edge coloring, direct product, matching.
2010 Mathematics Subject Classification: 05C15, 05C38.
References
| [1] | 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. |
| [2] | J.L. Baril, H. Kheddouci and O. Togni, Adjacent vertex distinguishing edge-colorings of meshes, Australasian J. Combin. 35 (2006) 89-102. |
| [3] | P.K. Jha, Kronecker products of paths and cycles: decomposition, factorization and bi-pancyclicity, Discrete Math. 182 (1998) 153-167, doi: 10.1016/S0012-365X(97)00138-6. |
| [4] | D.B. West, Introduction to Graph Theory, second ed. (Prentice Hall, Englewood Cliffs, NY, USA, 2001). |
| [5] | Z. Zhang, L. Liu and J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626, doi: 10.1016/S0893-9659(02)80015-5. |
Received 11 December 2008
Revised 2 March 2010
Accepted 8 August 2010
Close