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

DOI10.1007/S10898-015-0360-XMaRDI QIDQ288235zbMATH OpenOpenAlexFDO

Authors Danjun Huang, Yanwen Wang, Du Ding-Zhu, Weifan Wang, Yiqiao 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

treeouterplanar graphedge coloring2-distance vertex-distinguishing indexbreadth first search

Mathematics Subject Classification ID

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

Recommendations

• Legally \((\varDelta +2)\)-coloring bipartite outerplanar graphs in cubic time
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• scientific article; zbMATH DE number 432820
• Algorithms for finding distance-edge-colorings of graphs
• Computing and Combinatorics

Cites work

• scientific article; zbMATH DE number 5174935 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• Adjacent Vertex Distinguishing Edge‐Colorings
• Adjacent strong edge coloring of graphs
• Arbitrarily large difference between \(d\)-strong chromatic index and its trivial lower bound
• Introduction to algorithms.
• On Neighbor-Distinguishing Index of Planar Graphs
• On the vertex-distinguishing proper edge-colorings of graphs
• Some bounds on the neighbor-distinguishing index of graphs
• The surviving rate of an outerplanar graph for the firefighter problem
• Vertex-distinguishing proper edge-colorings
• \(L(h,1)\)-labeling subclasses of planar graphs
• \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
• \(d\)-strong edge colorings of graphs
• \(r\)-strong edge colorings of graphs

Cited in

(16)

• scientific article; zbMATH DE number 432820 (Why is no real title available?)
• Legally \((\varDelta +2)\)-coloring bipartite outerplanar graphs in cubic time
• On \(t\)-relaxed 2-distant circular coloring of graphs
• Two-distance vertex-distinguishing index of sparse graphs
• On graph proper total colorings with labelling-type restrictions
• An \(O(n\log n)\) algorithm for finding edge span of cacti
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• Distance vertex-distinguishing index of outerplanar graphs
• On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic
• 2-distance vertex-distinguishing index of subcubic graphs
• Algorithms for finding distance-edge-colorings of graphs
• Two-distance vertex-distinguishing index of sparse subcubic graphs
• Computing and Combinatorics
• 2-distance vertex-distinguishing total coloring of graphs
• Optimal \(r\)-dynamic coloring of sparse graphs
• On \(d_2\)-coloring of certain families of graphs

This page was built for publication: A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q288235)