Georgia Institute of Technology College of Sciences

As a generalization of Hamiltonicity problems, one may consider partitioning the vertices of a (directed) graph into as few paths (or cycles) as possible. Ore's classical theorem gives a tight upper bound on the number of paths needed to cover an n-vertex graph, with imbalanced bipartite graphs showing that the bound is best possible. A conjecture of Magnant and Martin (2009) suggests that Ore's bound can be significantly improved for regular graphs. This is also connected to the famous linear arboricity conjecture and has attracted considerable attention in recent years, including a very recent result establishing the conjecture up to a factor of two. In this talk, I will discuss directed and oriented variants of this conjecture and present some results in these settings. Based mostly on joint work with Allan Lo and Viresh Patel.