Thom Sulanke's 9-color example for Ringel's Earth–Moon problem. The problem concerns coloring a map of the Earth and Moon, subdivided into countries on the Earth with corresponding colonies on the Moon, so that each country has the same color as its colony and no two neighboring countries or colonies have the same color. Sulanke constructed this example of a map requiring nine colors, publicized by Martin Gardner in 1980. The graph representing the adjacencies between countries and colonies (center) is the join of a 6-vertex complete graph (top) and a 5-vertex cycle graph (bottom). All six vertices of the complete graph must have distinct colors, and an additional three colors are needed for the cycle.
Own work
David Eppstein