Harant, Jochen A note on Barnette’s conjecture. (English) Zbl 1291.05107 Discuss. Math., Graph Theory 33, No. 1, 133-137 (2013). 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. Cited in 2 Documents MSC: 05C38 Paths and cycles 05C40 Connectivity 05C45 Eulerian and Hamiltonian graphs 05C10 Planar graphs; geometric and topological aspects of graph theory Keywords:planar graph; Hamilton cycle; Barnette’s conjecture PDFBibTeX XMLCite \textit{J. Harant}, Discuss. Math., Graph Theory 33, No. 1, 133--137 (2013; Zbl 1291.05107) Full Text: DOI