Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface

DOI10.1016/j.dam.2010.06.019zbMath1208.05028OpenAlexW2013427304MaRDI QIDQ602768

Martin Kochol

Publication date: 5 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.06.019

zbMATH Keywords

edge-coloringapproximation algorithmspolyhedral embeddingorientable surfaceNP-complete problemcyclical edge-connectivity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Online Edge Coloring via Tree Recurrences and Correlation Decay

Cites Work

• Complexity of approximation of 3-edge-coloring of graphs
• Superposition and constructions of graphs without nowhere-zero \(k\)-flows
• Edge-coloring of multigraphs
• 3-Regular Non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces
• Polyhedral embeddings of snarks in orientable surfaces
• The NP-Completeness of Edge-Coloring
• Every Planar Map is Four Colorable
• Handbook of Graph Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item