When: Sunday, May 9, 10am
Where: Schreiber 309
Speaker: Gal Kronenberg,
Oxford University
Title:
Partitioning Cubic Graphs into Isomorphic Linear Forests
The linear arboricity of a graph $G$, denoted by la($G$), is the minimum number of edge-disjoint linear forests (i.e. collections of disjoint paths) in $G$ whose union is all the edges of $G$. It is known that the linear arboricity of every cubic graph is 2. In 1987 Wormald conjectured that every cubic graph with even number of edges, can be partitioned such that the two parts are isomorphic linear forests. This is known to hold for Jeager graphs and for some further classes of cubic graphs (see, Bermond-Fouquet-Habib-Peroche, Wormald, Jackson-Wormald, Fouquet-Thuillier-Vanherpe-Wojda). In this talk we will present a proof of Wormald's conjecture for all large connected cubic graphs.
This is joint work with Shoham Letzter, Alexey Pokrovskiy, and Liana Yepremyan.