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.

The main prerequisite to this talk is the desire to understand.