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:
Submitted by: Dan Archdeacon (with thanks to Henry Glover)
Send comments to dan.archdeacon@uvm.edu
November, 2003