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

作者：Yan Chengchao; Huang Danjun; Chen Dong; Wang Weifan^*

来源：Journal of Combinatorial Optimization, 2014, 28(4): 893-909.

DOI：10.1007/s10878-012-9569-5

• Adjacent vertex distinguishing edge coloring
• Planar graph
• Maximum degree
• Girth

An adjacent vertex distinguishing edge coloring of a graph is a proper edge coloring of such that any pair of adjacent vertices admit different sets of colors. The minimum number of colors required for such a coloring of is denoted by . In this paper, we prove that if is a planar graph with girth at least 5 and is not a 5-cycle, then , where is the maximum degree of . This confirms partially a conjecture in Zhang et al. (Appl Math Lett 15:623-626, 2002).

• 出版日期2014-11
• 单位浙江师范大学