科研之友
微信
新浪微博
Facebook
分享链接
摘要
Given a graph G, we study the problem of finding the minimum number of colors required for a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets consisting of colors of their incident edges. This minimum number is called the 2-distance vertex-distinguishing index, denoted by chi(d2)'(G). Using the breadth first search method, this paper provides a polynomial-time algorithm producing nearly-optimal solution in outerplanar graphs. More precisely, if G is an outerplanar graph with maximum degree., then the produced solution uses colors at most Delta + 8. Since chi(d2)'(G) >= Delta. for any graph G, our solution is within eight colors from optimal.
