###### Options

# Thoughts on Barnette's conjecture

Publikationstyp

Journal Article

Publikationsdatum

2016

Sprache

English

TORE-URI

Enthalten in

Volume

64

Start Page

354

End Page

365

Citation

The Australasian journal of combinatorics (2016)

Publisher Link

Publisher

Centre for Discrete Mathematics and Computing, Univ. of Queensland

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.

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.