Georgia Institute of Technology College of Sciences

A cubic graph is one where every vertex has degree three. A linear forest is a disjoint union of paths. It is known that the edge set of every cubic graph can be partitioned into two linear forests where each path is short (of constant size). A conjecture of Wormald asks for such a partition where the two forests are isomorphic (we no longer insist on having short paths, although that is also an open question). Note that this also can be phrased as an edge-colouring question. Is it possible to colour the edge set of a cubic graph by red and blue such that the two monochromatic components induce isomorphic linear forests? Recently we proved this for all connected graphs on a sufficiently large number of vertices. I will talk about the result and give some idea of the proof method. This is joint work with Gal Kronenberg, Shoham Letzter and Alexey Pokrovskiy.