Covering Graphs with Kuratowski Graphs



Let K(5) and K(3,3) denote the two Kuratowski graphs; that is, the minimal non-planar graphs. It is known that the disjoint union of k+1 Kuratowski graphs does not embed on the nonorientable surface of genus k formed by adding k crosscaps on the sphere. More subtly, one can often use k+1 Kuratowski subgraphs that have pairwise small intersection to prove that a graph does not embed on the nonorientable surface of genus k. Henry Glover asserts that such an argument can always be made.

Problem:  Suppose that G does not embed on the nonorientable surface  with k crosscaps. Then there is a subset of k+1  subgraphs G_1, ... ,G_{k+1} such that 1) each G_i is isomorphic to K(5) or to K(3,3), 2)  The union  of  any two G_i and G_j does not embed on the projective plane, and 3) the union of any three G_r, G_s, andG_t does not embed on either the Klein bottle or the  torus.

To verify the above problem for the surface of genus k, it suffices to check it for the irreducible graphs for that surface. These are the graphs that do not embed on the surface, but every propersubgraph does so embed.

The converse to the above problem may also be true. There is a graph that: a) embeds on the Klein bottle, b) is the union of three Kuratowski graphs such that c) the union of any two does not embed on the projective plane.

References:

Need the Richter Siran


Submitted by: Dan Archdeacon (with thanks to Henry Glover)

Send comments to dan.archdeacon@uvm.edu

November, 2003