�@�@Topological Graph Theory - Unsolved Problems

1. Does a graph is embeddable in the projective plane if it has a finite planar covering ? (Conjecture: YES)

   This is known as "the 1-2-infinity Conjecture". At the present, it has been shown that if K_1,2,2,2 has no finite planar covering, then the conjecture is true.

2. Does any triangulation on a closed surface of genus 2 of the maximum order contain a separating cycle of length 3 ? (Conjecture: YES)

   A triangulation is said to be irreducible if the contraction of any edge destroys its simpleness. In general, there exist only finitely many irreducible triangulations on each closed surface. If the conjecture is true, then we will obtain a good upper bound for the order of irreducible triangulations.

3. Embed two graphs on the projective plane so that each of them is embedded and that they cross each other at only their edges with crossing points as few as possible. Is the number of crossing points equal to the product of their edge representativities ? (Conjecture: YES) [Done!]

   The edge representativity of a graph embedded on the projective plane is defined as the minimum number of crossing points on its edges with a non-contractible simple closed curve which crosses only edges of the graph. It is easy to see that the minimum number of crossing points of two graphs does not exceed the product of their edge representativities.

   �� This conjecture has been already solved affirmatively in the following paper. Their proof is very nice and brief.
   

   D. Archdeacon and C.P. Bonnington, Two maps on one surface, preprint, 1997.

4. Draw a graph and its dual on its host surface, possibly not in the usual way, so that they cross each other at only their edges. and minimize the number of crossing points on their edges. It is clear that the number of crossing points does not exceed the number of edges. When do these two numbers coincide ?

   Similarly, consider the number of crossing points of a graph with itself. It might be interesting.

5. Does any spatial embedding of the n-cube with sufficiently large n contain a specified non-trivial knot or link ? Here we consider those spatial embeddings that all edges are straight line segments in the 3-space. (Conjecture: YES)

   The affirmative answer to the same question for the complete graphs and the complete bipartite graphs have been already shown.

6. Decide the maxmum looseness of triangulations on a closed surface with the complete graph K_n. (Conjecture: There is an upper bound for the looseness independent of n.)

   A triangulation on a closed surface is said to be n-loosely tight if any assignment of n+3 colors to its vertices induces a face with three distinct colors at its corners. The looseness of a triangulation is defined as the minimum n such that it is n-loosely tight. Any triangulation of looseness 0 is necessarily complete.

7. Determine the minimum value of the looseness taken over all the triangulations on a given closed surface.

   The solution of Map Color Theorem provides us with triangular embeddings of the complete graphs and such triangulations have looseness 0. Thus, the minimum in question is not increasing with respect to the genus of surfaces and come back to 0 with a suitable period.

8. Find a good operation which transform a pair of graphs embedded on a closed surface into each other if they have the same degree sequence.

   Among topological graph theory in Japan, "transformation of graphs" is very popular. This problem is one of extremal forms on such topics.

9. Consider a graph embedded on a closed surface with suitable metric and minimize the total sum of lengths of its edges within its isotopy class on the surface. Characterize those graphs such that there exist the limits which attain the minimum in their isotopy classes.

   For example, imagine a spider's web at a vertex. We will be able to shrink the web into the vertex, not changing the total sum of edge lengths. The limit of shringing the web is a graph, but is not isomorphic to the original. We want to know about graphs missing such a phenomenon.

10. A triangulation on a closed surface is pseudo-minimal if it cannot be transformed into any triangulation which has an contractible edge. Is there a pseudo-minimal triangulation which is not minimal ? (Conjecture: NO, but the correct answer is "YES".) [Done!]

    The concept of pseudo-minimality is very important in the theory of diagonal flips in triangulations, but, we don't know much about the concrete forms of pseudo-minimal triangulations.

    �� Recently, we have shown that K_4(m) and K_6(m) can be embedded on orientable and nonorientable closed surfaces, respectively, as their pseudo-minimal triangulations, using one of results in the following paper. Thusm the answer to the above question is "YES".
    

    D. Archdeacon, The medial graph and voltage-current duality, Discrete Math. 104 (1992) 111-141.

11. Is there a 6-connected triangulation on the nonorientable closed surface of genus 3 which has another inequivalent embedding on the surface ? (Conjecture: YES)

    There are infinitely many such 5-connected triangulations. Also, there are infinitely many 6-connected graphs each of which has at least two inequivalent embeddings on the nonorientable closed surface of genus 3.

12. Does a graph triangulate the projective plane if it admis a finite covering which is maximal planar. (Conjecture: YES)

    By simple calculation, we can show that such a covering should be 2-fold or 6-fold, and if it is 6-fold, then the graph cannot be embedded in the projective plane. The 1-2-infinity Conjectre will exclude this case. However, we want an elementary proof.

13. Suppose that two 3-connected graphs G and G^* can be embedded on a closed surface so that they are dual to each other. Is such a embedding unique? (Conjecture: YES)

    This will be an easy problem. There might be a pair of 2-connected graphs which have two or more such embeddings. First construct them. Next try to establish a theorem with suitable conditions, instead of "3-connected". The point is how relaxed those conditions are.