Seminar
On Graph Hamiltonicity: Counterexamples to Tutte's Conjecture -Part II, Alexander Kelmans, University of Puerto Rico, Mon, 27 October, 2008, 5:00 p.m. C-209
Abstract
Tutte conjectured in 1971 that every cubic, bipartite and 3-connected
graph has a cycle containing all vertices of the graph.
At the previous seminar we have discussed a construction that
provides infinitely many counterexamples to Tutte’s conjecture.
All such counterexamples have an essential edge 3-cut. Therefore
a natural question arises as to whether Tutte’s conjecture is true for
graphs without essential edge 3-cuts. We will show that Tutte’s
conjecture is not true even for graphs without essential edge 3-cuts.
Namely, we will describe some constructions providing infinitely many
counterexamples to the conjecture without essential edge 3-cuts. We will also discuss some known conjectures and put forward some
new conjectures and problems along this line.
Although this seminar is a continuation of the previous one,
the material of this seminar can be understood without the
knowledge of the previously discussed material. Graduate students from all mathematical areas
are very welcome.