Quotients of complete graphs: revisiting the Heawood map-coloring problem

Jonathan Light Gross and Thomas William Tucker

Vol. 55 (1974), No. 2, 391–402

DOI: 10.2140/pjm.1974.55.391

Abstract

The principal result of this paper is the determination of every graph that can be covered by a complete graph. It is shown that for every odd divisor d of the number n of vertices of a complete graph K_n, there is a unique graph with n∕d vertices covered by K_n, and that there are no other graphs covered by K_n. This determination is applied to an examination of certain aspects of the solution to the Heawood map-coloring problem. In particular, combinatorial arguments of the solution are set in a topological framework of branched covering spaces.

Mathematical Subject Classification 2000

Primary: 05C10

Milestones

Received: 2 May 1974

Published: 1 December 1974