On longest paths and cycles in graphs

In this talk I will present some recent work, joint with various collaborators, on longest paths and cycles in graphs. First, I will discuss three conjectures due to Lovasz (1969), Thomassen (1978) and Smith (1984), respectively, regarding the length and intersections of longest paths and cycles in (vertex-transitive) graphs, and present improved bounds towards these conjectures. If time permits, I will also present some recent new results on the corresponding problem for directed graphs.

Motivated by and related to these conjectures I will then present an improved upper bound for another well-known problem, going back to an old question of Gallai from 1966, namely: How many vertices are needed to hit all longest paths (cycles) in a connected (2-connected) graph?