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

DOI10.1007/s10898-015-0360-xzbMath1367.90108OpenAlexW1851117818MaRDI QIDQ288235

Danjun Huang, Yanwen Wang, Ding-Zhu Du, Wei Fan Wang, Yi Qiao Wang

Publication date: 25 May 2016

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-015-0360-x

zbMATH Keywords

treeedge coloringouterplanar graph2-distance vertex-distinguishing indexbreadth first search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15)

Related Items

Two-distance vertex-distinguishing index of sparse subcubic graphs, Optimal \(r\)-dynamic coloring of sparse graphs, Unnamed Item, 2-distance vertex-distinguishing total coloring of graphs, 2-distance vertex-distinguishing index of subcubic graphs, On \(t\)-relaxed 2-distant circular coloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arbitrarily large difference between \(d\)-strong chromatic index and its trivial lower bound
• The surviving rate of an outerplanar graph for the firefighter problem
• \(r\)-strong edge colorings of graphs
• On the vertex-distinguishing proper edge-colorings of graphs
• Adjacent strong edge coloring of graphs
• \(L(h,1)\)-labeling subclasses of planar graphs
• Some bounds on the neighbor-distinguishing index of graphs
• \(d\)-strong edge colorings of graphs
• \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
• Vertex-distinguishing proper edge-colorings
• Adjacent Vertex Distinguishing Edge‐Colorings
• On Neighbor-Distinguishing Index of Planar Graphs