In Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface it is proven that the task to find these colorings is NP-complete in the general case, except for planar graphs.
Is there any particular progress for bipartite cubic graphs made up of hexagons and octagons on a double torus?
Do efficient solutions exist in that particular case?