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.
DDC Class
510: Mathematik