1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I think I found what I need as comment in here, saying "Every bipartite graph has chromatic index $\Delta$"... $\endgroup$
    – draks ...
    Commented Jul 31, 2019 at 6:51
  • $\begingroup$ There may exist odd cycles non-contractable on the surface. $\endgroup$
    – LeechLattice
    Commented Jul 31, 2019 at 11:42
  • $\begingroup$ @Bullet51 but my graph is bipartite...? $\endgroup$
    – draks ...
    Commented Jul 31, 2019 at 11:50
  • 1
    $\begingroup$ A bipartite graph has chromatic index=maximum degree. For algorithms, see this. $\endgroup$
    – LeechLattice
    Commented Jul 31, 2019 at 13:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .