Open Problem Garden - Grunbaum's Conjecture - Comments

Solution (re: Grunbaum's Conjecture)

Anonymous — Mon, 23 Mar 2009 09:05:56 +0100

The solution of the Grunbaum's conjecture is published in (see also http://www.mat.savba.sk/~kochol):

M. Kochol, 3-Regular non 3-edge-colorable graphs with polyhedral embeddings in orientable surfaces, in: Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani, Lecture Notes in Computer Science, Vol. 5417, Springer-Verlag, Berlin, 2009, pp. 319-323

M. Kochol, Polyhedral embeddings of snarks in orientable surfaces, Proceedings of the American Mathematical Society vol. 137 (2009), pp. 1613-1619.

False in general (re: Grunbaum's Conjecture)

Anonymous — Wed, 19 Dec 2007 04:28:10 +0100

A counter example was found on the nine holed torus, and I have heard there is now one on the five holed torus as well so the conjecture is false in general. However what is still not known is for which n does the conjecture hold for the n-holed torus, and in particular the one holed torus is always of interest and remains open.

so ? (re: Grunbaum's Conjecture)

Anonymous — Mon, 17 Dec 2007 07:15:16 +0100

Sorry I don't understand, is the conjecture false or still opened ?

Wrong information. Martin (re: Grunbaum's Conjecture)

Anonymous — Sun, 25 Nov 2007 20:34:39 +0100

Wrong information. Martin Kochol

Grunbaum's conjecture is false! (re: Grunbaum's Conjecture)

Anonymous — Thu, 04 Oct 2007 03:00:44 +0200

Martin Kochol and Bojan Mohar announced a counterexample to Grunbaum's conjecture at the PIMS Workshop on the Cycle Double Cover Conjecture (Vancouver, 2007). By using Kochol's "superposition" operation on several copies of Petersen's graph, they constructed a snark which embeds on the orientable surface of genus 9, and whose dual contains no loops or parallel edges.

Of course Grunbaum's Conjecture may still hold true for lower-genus surfaces, in particular, the torus.

Ref: Kochol, M; Mohar, B; preprint 2007.

Grunbaum's Conjecture

mdevos — Wed, 04 Apr 2007 23:43:06 +0200

Author(s): Grunbaum

Subject: Graph Theory » Topological G.T. » Coloring

Conjecture If is a simple loopless triangulation of an orientable surface, then the dual of is 3-edge-colorable.