Partitioning cubic graphs into two isomorphic linear forests
Thursday, October 6, 2022 3:00 PM
Liana Yepremyan (Emory University)
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 from 80's 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 sufficiently large number of vertices. This is joint work with Gal Kronenberg, Shoham Letzter and Alexey Pokrovskiy.