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

DOI10.1007/S10898-015-0360-XzbMATH Open1367.90108OpenAlexW1851117818MaRDI QIDQ288235FDOQ288235

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

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

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)

Cites Work

• Introduction to algorithms.
• Adjacent strong edge coloring of graphs
• Vertex-distinguishing proper edge-colorings
• Title not available (Why is that?)
• On the vertex-distinguishing proper edge-colorings 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
• Arbitrarily large difference between \(d\)-strong chromatic index and its trivial lower bound
• Title not available (Why is that?)
• Adjacent Vertex Distinguishing Edge‐Colorings
• On Neighbor-Distinguishing Index of Planar Graphs
• The surviving rate of an outerplanar graph for the firefighter problem
• \(r\)-strong edge colorings of graphs

Cited In (16)

• 2-distance vertex-distinguishing total coloring of graphs
• An \(O(n\log n)\) algorithm for finding edge span of cacti
• Algorithms for finding distance-edge-colorings of graphs
• 2-distance vertex-distinguishing index of subcubic graphs
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• Two-distance vertex-distinguishing index of sparse graphs
• Title not available (Why is that?)
• On \(t\)-relaxed 2-distant circular coloring of graphs
• Legally \((\varDelta +2)\)-coloring bipartite outerplanar graphs in cubic time
• Computing and Combinatorics
• Two-distance vertex-distinguishing index of sparse subcubic graphs
• On graph proper total colorings with labelling-type restrictions
• Distance vertex-distinguishing index of outerplanar graphs
• On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic
• 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)