双圈图的D(2)-点可区别边染色

D(2)-vertex-distinguishing edge coloring of bicyclic graphs

图G的一个正常k-边染色f满足对■u,v∈V(G),当d(u,v)≤2时都有S_(f)(u)≠S_(f)(v),其中S_(f)(v)={f(vw)|vw∈E(G)}表示顶点v的所有关联边上所染颜色构成的集合,则称f为图G的k-D(2)-点可区别边染色(简记为k-D(2)-VDEC),将其所需要颜色的最小数k称为D(2)-点可区别边色数,简记为χ’_(2-vd)(G).结合Hall定理证明了最大度为△(G)的双圈图G都有χ’_(2-vd)(G)≤△(G)+2.

A proper k-edge-coloring f of a graph G is said to be k-D(2)-vertex distinguishing edge coloring(k-D(2)-V DEC for short)if any two vertices u,v 2 ∈(G)with d(u,v)≤2 satisfy S_(f)(u)6≠S_(f)(v),where S_(f)(v)={f(vw)jvw 2 E(G)} denote the set of colors assigned on the edges incident to a vertex v.The minimum number k required for a D(2)-vertex distinguishing edge coloring of G is called the D(2)-vertex distinguishing edge chromatic number,and denoted byχ’_(2-vd)(G).In this paper,combining with Hall's theorem,it is proved thatχ’_(2-vd)(G)·≤(G)+2 for any bicyclic graph G with maximum degree¢(G).