Decomposing cubic graphs into isomorphic linear forests

Abstract

In 1987 Wormald conjectured that the edges of every cubic graph on 4n vertices can be partitioned into two isomorphic linear forests. We prove this conjecture for large connected cubic graphs. This is joint work with Gal Kronenberg, Alexey Pokrovskiy, and Liana Yepremyan.

Speaker Intro

Shoham Letzter is a Royal Society University Research Fellow and lecturer at University College London (UCL). Before joining UCL in 2020, she was a Junior Fellow at the ETH Institute for Theoretical Studies, and a Junior Research Fellow in Murray Edwards College, Cambridge. She received her PhD in 2015 from the University of Cambridge, under the supervision of Béla Bollobás. Her main research interests are in extremal and probabilistic combinatorics.