Hamiltonian cycles in some family of cubic 3-connected plane graphs
Volume 151 / 2018
Colloquium Mathematicum 151 (2018), 229-274
MSC: 05C45, 05C05.
DOI: 10.4064/cm7123-9-2017
Published online: 20 December 2017
Abstract
Barnette conjectured that all cubic 3-connected plane graphs with maximum face size at most 6 are hamiltonian. We provide a method of construction of a hamiltonian cycle in an arbitrary 3-connected cubic plane graph possessing a face $f$ (of arbitrary size) such that every face incident with $f$ is bounded by at most five edges and any other face is bounded by at most six edges. The method works for a larger family of graphs where many faces may have arbitrary sizes.
