The Four-Color-Theorem is equivalent to the fact that every 3-connected cubic planar graph is 3-edge-colorable. For any other surface S, there are snarks (non-3-edge-colorable cyclically 4-edge-connected cubic graphs of girth at least 5) whose minimum genus embedding is in S. My student Andrej Vodopivec recently proved that there are infinitely many nonisomorphic snarks that can be embedded in the torus. This fact also implies that for every positive integer g there are infinitely many snarks of genus g.
During the 21st LL-seminar in Celovec (Klagenfurt) in Austria, I asked the following unresolved question:
Problem: Determine all snarks that can be embedded in the projective plane.
I would not be surprised if the Petersen graph is the only projective snark.
Send comments to Bojan.Mohar@uni-lj.si