On Barnette's Conjecture

We prove a new sufficient condition for a cubic 3-connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let G be a planar triangulation. Then the dual of G is a cubic 3-connected planar graph G*, and G* is bipartite if and only if G is Eulerian.

We prove that if the vertices of G are (improperly) colored blue and red, such that the blue vertices cover the faces of G, there is no blue cycle, and every red cycle contains a vertex of degree at most 4, then G* is Hamiltonian.

This result solves a special case of Barnette's Conjecture; we also highlight the limitations of using a coloring of G as a starting point for proving Barnette's Conjecture.

joint work with Helmut Alt, Michael Payne and David Wood