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

Weifan Wang (), Danjun Huang (), Yanwen Wang, Yiqiao Wang () and Ding-Zhu Du ()
Additional contact information
Weifan Wang: Zhejiang Normal University
Danjun Huang: Zhejiang Normal University
Yanwen Wang: Zhejiang Normal University
Yiqiao Wang: Beijing University of Chinese Medicine
Ding-Zhu Du: Ton Duc Thang University

Journal of Global Optimization, 2016, vol. 65, issue 2, No 9, 367 pages

Abstract: 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)$$ χ d 2 ′ ( 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$$ Δ + 8 . Since $$\chi '_{d2}(G)\ge \varDelta $$ χ d 2 ′ ( G ) ≥ Δ for any graph G, our solution is within eight colors from optimal.

Keywords: Breadth first search; Tree; Outerplanar graph; Edge coloring; 2-Distance vertex-distinguishing index (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-015-0360-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:65:y:2016:i:2:d:10.1007_s10898-015-0360-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-015-0360-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().