Approximation of 3-Edge-Coloring of Cubic Graphs

DOI10.1016/J.ENDM.2007.07.016MaRDI QIDQ3503456zbMATH OpenOpenAlexFDO

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

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2007.07.016

zbMATH Keywords

3-edge-coloring3-regular graphapproximation algorithmcyclical edge-connectivityNP-completeness

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Complexity of approximation of 3-edge-coloring of graphs
• Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
• Approximating the maximum 3- and 4-edge-colorable subgraph (extended abstract)
• Determining the total colouring number is NP-hard
• A polyhedral approach to edge coloring

Cites work

• A cyclically 6-edge-connected snark of order 118
• Edge-coloring of multigraphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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

(8)

• A polyhedral approach to edge coloring
• Reflexive coloring complexes for 3-edge-colorings of cubic graphs
• Three-edge-colouring doublecross cubic graphs
• Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
• Edge-coloring of 3-uniform hypergraphs
• On the hardness of computing span of subcubic graphs
• Determining the total colouring number is NP-hard
• Complexity of approximation of 3-edge-coloring of graphs

This page was built for publication: Approximation of 3-Edge-Coloring of Cubic Graphs

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