## Abstract

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 Conjecture: 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 Barnette's Conjecture that were obtained by Kelmans and for which detailed self-contained proofs have not been published.

Original language | English |
---|---|

Pages (from-to) | 354-365 |

Number of pages | 12 |

Journal | Australasian Journal of Combinatorics |

Volume | 64 |

Issue number | 2 |

Publication status | Published - 2016 |