Partitioning cubic graphs into isomorphic linear forests

Abstract: 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 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.

Armeniancombinatorics

Audience: general audience

( slides | video )

Comments: Talk chair: Petros Petrosyan

---

Yerevan Mathematical Colloquium

Series comments: "Yerevan Mathematical Colloquium" invites survey talks aimed at a general mathematical audience, that emphasize proof methods, relations between branches of mathematics, possible applications, and open problems.

---