Complexity of approximation of 3-edge-coloring of graphs

DOI10.1016/J.IPL.2008.05.015MaRDI QIDQ975462zbMATH OpenOpenAlexFDO

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

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

approximation algorithmsNP-completenesscyclical edge-connectivityedge-coloring of graphs

Mathematics Subject Classification ID

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

Recommendations

• Approximation of 3-Edge-Coloring of Cubic Graphs
• On the hardness of approximating the chromatic number
• Approximating the maximum 3- and 4-edge-colorable subgraph (extended abstract)
• Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
• Determining the total colouring number is NP-hard

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A cyclically 6-edge-connected snark of order 118
• Experimental and Efficient Algorithms
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Superposition and constructions of graphs without nowhere-zero k-flows
• The NP-Completeness of Edge-Coloring

Cited in

(7)

• Deciding 3-colourability in less than O(1.415n) steps
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Three measures of edge-uncolorability
• Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• On the complexity of deciding whether the regular number is at most two
• Approximation of 3-Edge-Coloring of Cubic Graphs

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

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