×

A note on Barnette’s conjecture. (English) Zbl 1291.05107

Summary: Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is Hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant \(c > 0\) such that each graph \(G\) of this class contains a path on at least \(c|V (G)|\) vertices.

MSC:

05C38 Paths and cycles
05C40 Connectivity
05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI