Edge-decomposition of cubic graphs into two 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. In the second part of this talk, I will give some ideas used in the proof and demonstrate how we prove an approximate result (as a first step to our proof of the general result). This is joint work with Gal Kronenberg, Shoham Letzter and Alexey Pokrovskiy.

combinatorics

Audience: general audience

( slides )

Comments: Rescheduling: The talk was originally scheduled for Apr 2nd. It is now rescheduled to Apr 9th. Talk host: 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.

---