We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs.
- Authors
Wang, Weifan; Huang, Danjun; Wang, Yanwen; Wang, Yiqiao; Du, Ding-Zhu
- Abstract
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 $$\varDelta $$ , then the produced solution uses colors at most $$\varDelta +8$$ . Since $$\chi '_{d2}(G)\ge \varDelta $$ for any graph G, our solution is within eight colors from optimal.
- Subjects
ALGORITHM research; ALGEBRA; GRAPH theory; GEOMETRY; COMBINATORICS
- Publication
Journal of Global Optimization, 2016, Vol 65, Issue 2, p351
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-015-0360-x