Barnette's Conjecture

Barnette's conjecture asserts that every 3-connected bipartite cubic planar graph is Hamiltonian. The only graph on nine or fewer vertices satisfying Barnette's conditions is the cubical graph, which is indeed Hamiltonian. The skeletons of the truncated octahedron, great rhombicuboctahedron, and great rhombicosidodecahedron also satisfy the conditions and, since they are Archimedean solids, are indeed Hamiltonian. Holton et al. (1985) proved that all graphs having fewer than 66 vertices satisfy the conjecture, but the general conjecture remains open.

Similarly, Barnette conjectured that all cubic, 3-connected, planar graphs with a face size of at most 6 are Hamiltonian. Aldred et al. (2000) have verified this conjecture for all graphs with fewer than 177 vertices.

REFERENCES

Aldred, R.; Bau, S.; Holton, D., and McKay, B. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.

Barnette, D. Conjecture 5 in Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968 (Ed. W. T. Tutte). New York: Academic Press, 1969.

Holton, D.; Manvel, B.; and McKay, B. "Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs." J. Combin. Th. Ser. B 38, 279-297, 1985.

Owens, P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Disc. Math. 44, 327-330, 1983.