Adjacent vertex distinguishing edge coloring of brick-product of graphs

Year 2021, Volume: 3 Issue: 1, 1 - 14, 02.06.2021

Anantharaman S

Abstract

The graph $G$ to be a finite, simple, undirected and connected. An edge coloring of a graph $G$ is an assignment of colors of $G,$ one color to each edge. If adjacent edges are assigned distinct colors, then the edge coloring is a proper edge coloring. The adjacent vertex distinguishing proper edge coloring is the minimum number of colors required for a proper edge coloring of a graph $G$ such that adjacent vertices are distinguished by their color sets (colors of edges that are incident to them). The minimum number of colors required for an adjacent vertex distinguishing proper edge coloring of a graph is called the adjacent vertex distinguishing chromatic index. In this paper, I am computing adjacent vertex distinguishing chromatic index of brick-product of graphs.

Keywords

Edge coloring, Adjacent vertex distinguishing chromatic index, Brick-product

References

• M. Axenovich, J. Harant, J. Przybylo, R. Soták, M. Voigt, J. Weidelich, A note on adjacent vertex distinguishing colorings of graphs, {\it Discrete Appl. Math.} {\bf 205} (2016) 1-7.
• R. Balakrishnan, K. Ranganathan, {\it A textbook of graph theory,} Second Edition, Springer, New York, 2012.
• P.N. Balister, E. Gyori, J. Lehel, R.H. Schelp, Adjacent vertex distinguishing edge coloring, {\it SIAM J. Discrete Math.} {\bf 21} (1) (2007) 237-250.
• J.L. Baril, H. Kheddouci, O. Togni, Adjacent vertex distinguishing edge coloring of meshes, {\it Australasian J. Combin.} {\bf 35} (2006) 89-102.
• Y. Bu, K. Lih, W. Wang, Adjacent vertex distinguishing edge colorings of planar graphs with girth at least six, {\it Discuss. Math. Graph Theory} {\bf 31} (2011) 429-439.
• X. Chen, Z. Li, Adjacent-vertex-distinguishing proper edge coloring of planar bipartite graphs with $\Delta=9,$ $10,$ or $11,$ {\it Inform. Process. Lett.} {\bf 115} (2015) 263-268.
• H. Hatami, $\Delta+300$ is a bound on the adjacent vertex distinguishing edge chromatic number, {\it J. Combin. Theory Ser. B} {\bf 95} (2005) 246-256.
• H. Hocquard, M. Montassier, Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five$^1,$ {\it Electron. Notes Discrete Math.} {\bf 38} (2011) 457-462.
• W. Imrich, S. Klavzar, {\it Product graph: structure and recognition,} Wiley Interscience, New York 2000.
• J. Li, Z. Zhang, X. Chen, Y. Sun, A Note on adjacent strong edge coloring of $K(n,m),$ {\it Acta Math. Appl. Sin. Engl. Ser.} {\bf 22} (2) (2006) 273-276.
• B. Lin, G. Liu, On the adjacent vertex distinguishing edge coloring of graphs, {\it Int. J. Comput. Math.} {\bf 87} (4) (2010) 726-732.
• L. Lin-zhong, L. Yin-zhen, Z. Zhong-fu, W. Jian-fang, On the adjacent strong edge coloring of Halin Graphs, {\it Journal of Mathematical Research} \& {\it Exposition} {\bf 23} (2) (2003) 241-246.
• M.M. Omai, S.M. de Almeida, D. Sasaki, AVD-edge coloring on power of path$^1,$ {\it Electron. Notes Discrete Math.} {\bf 62} (2017) 273-278.
• Z. Shao, J. Xu, R. K. Yeh, L(2,1)-labeling for brick product graphs, {\it J. Comb. Optim.} {\bf 31} (2) (2016) 47–462.
• W. Wang, Y. Wang, Adjacent vertex distinguishing edge colorings of graphs with smaller maximum average degree, {\it J. Comb. Optim.} {\bf 19} (2010) 471-485.
• X. Yu, C. Qu, G. Wang, Y. Wang, Adjacent vertex distinguishing colorings by sum of sparse graphs, {\it Discrete Math.} {\bf 339} (2016) 62-71.
• Z. Zhang, L. Liu, J. Wang, Adjacent Strong Edge Coloring of Graphs, {\it Appl. Math. Lett.} {\bf 15} (2002) 623–626.
• L. Zhang, W. Wang, K. Lih, An improved upper bound on adjacent vertex distinguishing chromatic index of a graph, {\it Discrete Appl. Math.} {\bf 162} (2014) 348-354.