School of Mathematical Sciences

Path partitions of regular graphs menu

Path partitions of regular graphs

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.