Adjacent vertex distinguishing edge-coloring of planar graphs with girth at least five

作者：Xu Xinping; Zhang Yiying^*

来源：Ars Combinatoria, 2014, 116: 359-369.

• Edge-coloring
• vertex-distinguishing
• planar graphs

An adjacent vertex-distinguishing edge coloring, avd-coloring for short, of a graph G is a proper edge coloring of G such that no pair of adjacent vertices are incident to the same set of colors. We use chi(avd)'(G) to denote the avd-chromatic number of G which is the smallest integer k such that G has an avd-coloring with k-colors, and use Delta(G) to denote the maximum degree of G. In this paper, we prove that chi(avd)'(G) <= Delta(G) + 4 for every planar graph G without isolated edges whose girth is at least five. This is nearly a sharp bound since chi(avd)'(C-5) = Delta(C-5) + 3.

• 出版日期2014-7
• 单位南京师范大学