TR06-015 Authors: Tomas Feder, Carlos Subi

Publication: 6th February 2006 05:52

Downloads: 594

Keywords:

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,\ldots$ 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.