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 Kn. Then the dual cubic graph is 3-edge-colorable.
Let me observe that the dual of the complete graph K6 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