Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
From MaRDI portal
Publication:602768
DOI10.1016/j.dam.2010.06.019zbMath1208.05028MaRDI QIDQ602768
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
edge-coloring; approximation algorithms; polyhedral embedding; orientable surface; NP-complete problem; cyclical edge-connectivity
05C15: Coloring of graphs and hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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