A graph G covers a graph H if there exists a graph map f from G to H such that the edges incident with a vertex v map bijectively to those incident with u = f(v). The set f^{-1} (u) is called the fiber above u. If H is connected, which we shall assume, then the size of each fiber is a constant called the fold number of the covering.

For example, the dodecahedron is a 2-fold cover of the Petersen graph. The fiber above a Petersen vertex consists of two vertices of distance 5 in the dodecahedron. More strongly, taking the usual embedding of the dodecahedron in the sphere and identifying all spherical antipodal points yields an embedding of the Petersen graph in the projective plane.

Any graph H which embeds in the projective plane has a planar covering graph G created by the spherical antipodal double covering of the projective plane described above. The following conjecture from [N1] states that this sufficient condition is also necessary.

Conjecture: A graph has a planar cover if and only if it embeds in the projective plane.

As a corollary, if a graph has a planar cover, then it has a 2-fold planar cover. So the minimum fold number among all planar covers is either 1, 2, or infinity, hence the name the 1-2-infinity Conjecture.

Note that the property of having a planar cover is hereditary under the minor ordering. So to proove the conjecture it suffice to show that the 35 minor-minimal non-projective-planar graphs (see [A]) have no planar covers. Some of these 35 cases have been done directly. Some cases reduce to others. For roughly eight years there were only two remaining cases: K_7 - 3 K_2 = K_{1,2,2,2} and K_{4,4} - K_2. These were called the ``terrible two''. However, Petr Hlineny [H] has shown K_{4,4} - K_2 has no planar cover, so the sole remaining case is K_{1,2,2,2} (the ``obnoxious one''.) It was recently announced that the last case had been solved, ending the conjecture, but announced proof had a flaw and was withdrawn. The case remains open.

Known partial results are due to Archdeacon, to Fellows (personal communication), and to Negami [N2]. Fellows points out an application to computer science where the covering graph G can be used to ``emulate'' a computer arrchitecture H by having each vertex v do the calculations normally performed by u = f(v). Phil Huneke has written a note on this conjecture which appeared in the proceedings of the Seattle Graph Minors Conference Contemp. Math. 147 AMS.

I'm unclear about the exact connection with the related conjecture: ``No nonplanar graph has an odd-fold planar cover''. [Does the related conjecture follow from work by Richter and Archdeacon?]

[A] D. Archdeacon, A Kuratowski theorem for the projective plane, J. Graph Theory 5 (1981) 243-246.

[N1] S. Negami, The spherical genus and virtually planar graphs, Discrete Math. 70 (1988) 159-168.

[N2] S. Negami, Graphs which have no finite planar covering, Bull. of the Inst. of Math. Academia Sinica 16 (1988) 377-384.

[H] P. Hlineny, (need this reference, JCTB?)

Submitted by: Dan Archdeacon, Department of Math. And Stat., University of Vermont, Burlington, VT, USA 05405

Send comments to dan.archdeacon@uvm.edu