On Barnette's conjecture
Tomás Feder, Carlos Subi · 2006
Barnette’s conjecture is the statement that every 3-connected cubic planar bipartite graph is Hamiltonian. Goodey showed that the conjecture holds when all faces of the graph have either 4 or 6 sides. We generalize Goodey’s result by showing that when the faces of such a graph are 3-colored, with adjacent faces having different colors, if two of the three color classes contain only faces with either 4 or 6 sides, then the conjecture holds. More generally, we consider 3-connected cubic planar graphs that are not necessarily bipartite, and show that if the faces of such a graph are 2-colored, with every vertex incident to one blue face and two red faces, and all red faces have either 4 or 6 sides, while the blue faces are arbitrary, provided that blue faces with either 3 or 5 sides are adjacent to a red face with 4 sides (but without any assumption on blue faces with 4,6,7,8,9,... sides), then the graph is Hamiltonian. The approach is to consider the reduced graph obtained by contracting each blue face to a single vertex, so that the reduced graph has faces corresponding to the original red faces and with either 2 or 3 sides, and to show that such a reduced graph always contains a proper quasi spanning tree of faces. In general, for a reduced graph with arbitrary faces, we give a polynomial time algorithm based on spanning tree parity to decide if the reduced graph has a spanning tree of faces having 2 or 3 sides, while to decide if the reduced graph has a spanning tree of faces with 4 sides or of arbitrary faces is NP-complete for reduced graphs of even degree. As a corollary, we show that whether a reduced graph has a noncrossing Euler tour has a polynomial time algorithm if all vertices have degree 4 or 6, but is NP-complete if all vertices have degree 8. Finally, we show that if Barnette’s conjecture is false, then the question of whether a graph in the class of the conjecture is Hamiltonian is NP-complete. 1