Combinatorics Seminar

When: Sunday, December 24, 10am Where: Schreiber 309 Speaker: Shoham Letzter, ETH-ITS Title: Path partitions of regular graphs

Abstract:

The well-known theorem of Dirac (1952) states that a graph on n vertices with minimum degree at least n/2 contains a Hamilton cycle. As a possible generalisation of Dirac's result, Magnant and Martin (2009) conjectured that every k-regular graph on n vertices can be partitioned into at most n/(k+1) paths, a bound which is attained by a disjoint union of k+1 cliques. Note that the regularity assumption is needed in order to allow for a partition into a small number of paths, as otherwise a sufficiently unbalanced bipartite graph is a counter example. We prove this conjecture in the case where k is linear in n and n is large.

This talk is based on joint work with Vytautas Gruslys.