Variations on Ringel's earth-moon problem

摘要

We use current graphs to find decompositions of complete graphs into subgraphs with certain embeddability properties. These decompositions provide solutions to various extensions of Ringel's earth-moon problem to other surfaces and to more than two surfaces. In particular, we find a decomposition of K_(6n + 1) into n toroidal graphs, and from this get a decomposition of K_(6n) into n projective-plane graphs. We find a decomposition of K_(19) into three Klein bottle graphs and for n > 3, we also conjecture that there exist decompositions of K_(6n + 1) into n Klein bottle graphs. Finally, we find the 3-chromatic number for infinitely many different orientable surfaces.