Complexity of approximation of 3-edge-coloring of graphs
From MaRDI portal
Publication:975462
DOI10.1016/J.IPL.2008.05.015zbMATH Open1191.68468OpenAlexW2004299695MaRDI QIDQ975462FDOQ975462
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
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
- Title not available (Why is that?)
- The NP-Completeness of Edge-Coloring
- Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
- Superposition and constructions of graphs without nowhere-zero \(k\)-flows
- A cyclically 6-edge-connected snark of order 118
- Experimental and Efficient Algorithms
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)
