Graph Theory Seminar

Thursday, June 14, 2018 3:30 pm - 3:30 pm EDT (GMT -04:00)

Title: Hamilton cycles in cubic planar graphs

Speaker: Frantisek Kardos
Affiliation: University of Bordeaux
Room: MC 5479

Abstract: Tait conjectured in 1884 that each cubic planar graph contains a Hamilton cycle. Had the conjecture been true, it would have implied the Four Color Theorem. However, it was disproved by Tutte in 1946. Later on, other counterexamples with different structural properties were found. On the other hand, for several subclasses of cubic planar graphs Hamiltonicity was proven. In general, the problem of founding a Hamilton cycle in a cubic planar graph turned out to be NP-complete.

All known counterexamples to Tait's conjecture contain (i) odd cycles and (ii) faces of large size. That's why Barnette formulated in the 60s two conjectures in the form of sufficient conditions for the Hamiltonicity of cubic planar graphs: He conjectured that bipartite cubic planar graphs, as well as cubic planar graphs with faces of size at most 6, are Hamiltonian. We will present results, methods and ideas leading to a computer-assisted proof of the latter.