Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree

作者：Wang Weifan; Wang Yiqiao

来源：Journal of Combinatorial Optimization, 2010, 19(4): 471-485.

DOI：10.1007/s10878-008-9178-5

• Adjacent vertex distinguishing edge-coloring
• Graph
• Maximum average degree
• Maximum degree

An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by chi(a)'(G). Letmad(G) and Delta denote the maximum average degree and the maximum degree of a graph G, respectively. In this paper, we prove the following results: (1) If mad(G) < 3 and Delta >= 3, then chi(a)'(G) <= Delta + 2. (2) If mad(G) < 5/2 and Delta >= 4, or mad(G) < 7/3 and Delta >= 3, then chi(a)'(G) <= Delta + 1. (3) If mad(G) < 5/2 and Delta >= 5, then chi(a)'(G) = Delta+ 1 if and only if G contains adjacent vertices of maximum degree.

• 出版日期2010-5
• 单位浙江师范大学