Thoughts on Barnette's conjecture

Alt, Helmut GND; Payne, Michael S.; Schmidt, Jens M. GND; Wood, David R.

We prove a new sufficient condition for a cubic 3-connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let G be a planar triangulation. Then the dual G∗ is a cubic 3-connected planar graph, and G∗ is bipartite if and only if G is Eulerian. We prove that if the vertices of G are (improperly) coloured blue and red, such that the blue vertices cover the faces of G, there is no blue cycle, and every red cycle contains a vertex of degree at most 4, then G∗ is Hamiltonian. This result implies the following special case of Barnette’s Conjec- ture: if G is an Eulerian planar triangulation, whose vertices are properly coloured blue, red and green, such that every red-green cycle contains a vertex of degree 4, then G∗ is Hamiltonian. Our final result highlights the limitations of using a proper colouring of G as a starting point for proving Barnette’s Conjecture. We also explain related results on Bar- nette’s Conjecture that were obtained by Kelmans and for which detailed self-contained proofs have not been published.

Cite

Citation style:
Alt, H., Payne, M.S., Schmidt, J.M., Wood, D.R., 2016. Thoughts on Barnette’s conjecture. The Australasian journal of combinatorics, The Australasian journal of combinatorics 64, 2016, 354–365.
Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:
All rights reserved

Export