Complexity of approximation of 3-edge-coloring of graphs

DOI10.1016/J.IPL.2008.05.015zbMath1191.68468OpenAlexW2004299695MaRDI QIDQ975462

Katarína Šranková, Nad'a Krivoňáková, Silvia Smejová, Martin Kochol

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.05.015

zbMATH Keywords

NP-completenessapproximation algorithmscyclical edge-connectivityedge-coloring of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (3)

Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface ⋮ Three measures of edge-uncolorability ⋮ On the complexity of deciding whether the regular number is at most two

Cites Work

• Unnamed Item
• A cyclically 6-edge-connected snark of order 118
• Superposition and constructions of graphs without nowhere-zero \(k\)-flows
• The NP-Completeness of Edge-Coloring
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Experimental and Efficient Algorithms

This page was built for publication: Complexity of approximation of 3-edge-coloring of graphs