## Duals of Complete Graph Triangulations and Snarks

Instead of an excuse for the Summer delay, I start with some personal touch.

At the
moment of preparing this HTML file, I am sitting on the balcony of an apartment in
a little (used-to-be) fisherman village Metajna on the island Pag in Croatia. Click on
thumbnails below to check for the beautiful view I enjoy at this time (taken with my notebook's built-in
camera). It is vacation time and extreeeemely hot (in the 30's also during the
night, so that I have to sleep outside). In the mornings and evenings I steal some time to
work, in the mid-day I follow the *siesta* habits, while in the afternoon,
when winds get stronger, I do some wind surfing in
the inlet that you can see on the photo below.

Going back to Math, I made the conjecture stated below after a discussion with my student
Andrej Vodopivec a few weeks ago. It is a specific case of Grünbaum's Conjecture
(see the July 2001 problem).

**Conjecture:** Let *K*
be a triangulation of an orientable surface whose underlying graph is the
complete graph *K*_{n}. Then the dual cubic graph is
3-edge-colorable.

Let me observe that the dual of the complete graph *K*_{6}
embedded in the projective plane is the Petersen graph. I would dare to
conjecture that this is the only counterexample to the nonorientable counterpart
of the above conjecture.

An embedding of a graph G in some surface is said to be *polyhedral *
if every facial boundary is a cycle in the graph and any
two distinct faces share at most a vertex or an edge in
their boundaries. It is easy to see that an embedding is polyhedral if and only
if the graph is 3-connected and the face-width is at least 3. A polyhedral map
is *contraction critical* if the contraction of any edge gives rise to a
nonpolyhedral map.

**Problem:** What
can be said about cubic contraction critical polyhedral maps? Are they
3-edge-colorable? Is asking this equivalent to Grünbaum's Conjecture?

If G is the dual graph of a complete graph triangulation, then every pair of
faces have an edge in common. This implies that G is a contraction critical cubic
map.

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: avgust 18, 2003.