Planar Covering Graphs: the 1-2-infinity Conjecture

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 prove 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 [F] 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 [H] has written a note on this conjecture. A related result [AR] is ``No nonplanar graph has an odd-fold planar cover''.

References:

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

[AR] D. Archdeacon, R.B. Richter, On the parity of planar covers, J. Graph Theory 14 (1990) 199-204

[F] M. Fellows, Planar emulators and planar covers, manuscript (1988)

[H] J.P. Huneke, A conjecture in topological graph theory, Graph Structure Theory, Comtemp. Math. 147 (1993) 387-389.

[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, K_{4,4}-e has no finite planar cover, J. of Graph Theory 27 (1998) 51-60

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