A note on Barnette’s conjecture

A well-known conjecture of Barnette states that every 3-connected cubic bipartite planar graph has a Hamiltonian cycle, which is equivalent to the statement that every 3-connected even plane triangulation admits a 2-tree coloring, meaning that the vertices of the graph have a 2-coloring such that each color class induces a tree. In this paper we present a new approach to Barnette’s conjecture by using 2-tree coloring. ette triangulation is a 3-connected even plane triangulation, and a B-graph is a smallest Barnette triangulation without a 2-tree coloring. A configuration is reducible if it cannot be a configuration of a B-graph. We prove that certain configurations are reducible. We also define extendable, non-extendable and compatible graphs; and discuss their connection with Barnette’s conjecture.