Speaker:

Vytautas Gruslys (University of Cambridge)

Date/Time:

Fri, 20/10/2017 - 16:00

Room:

W316, Queen's Building

Seminar series:

We consider the problem of covering a regular graph by a small number of vertex-disjoint paths. Magnan and Martin 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. We prove the conjecture in the case where k is linear in n and n is large.

This talk is based on joint work with Shoham Letzter.