Adjacent vertex distinguishing indices of planar graphs without 3-cycles

作者：Huang Danjun; Miao Zhengke; Wang Weifan^*

来源：Discrete Mathematics, 2015, 338(3): 139-148.

DOI：10.1016/j.disc.2014.10.010

• Adjacent vertex distinguishing coloring
• Planar graph
• Maximum degree
• Cycle

Given a proper edge k-coloring phi and a vertex v is an element of V (G), let C phi (v) denote the set of colors used on edges incident to v with respect to phi. The adjacent vertex distinguishing index of G, denoted by chi(1)(a) (G), is the least value of k such that G has a proper edge k-coloring which satisfies C phi (u) not equal C phi (v) for any pair of adjacent vertices u and v. In this paper, we show that if G is a connected planar graph with maximum degree Delta >= 12 and without 3-cycles, then Delta <= chi(1)(a) <= Delta+1, and chi(1)(a) = Delta + 1 if and only if G contains two adjacent vertices of maximum degree. This extends a result in Edwards et al. (2006), which says that if G is a connected bipartite planar graph with Delta >= 12 then chi(1)(a) <= Delta + 1.

• 出版日期2015-3-6
• 单位浙江师范大学