A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs

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 ${\mathit{\chi }}_{d2}^{\prime }(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 $\mathit{\Delta }$ , then the produced solution uses colors at most $\mathit{\Delta }+8$ . Since ${\mathit{\chi }}_{d2}^{\prime }(G)\ge \mathit{\Delta }$ for any graph G, our solution is within eight colors from optimal.