When: Sunday, December 24, 10am
Where: Schreiber 309
Speaker: Shoham Letzter, ETH-ITS
Title: Path partitions of regular graphs
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.