Decomposing cubic graphs into isomorphic linear forests
| Autor: | Kronenberg, Gal, Letzter, Shoham, Pokrovskiy, Alexey, Yepremyan, Liana |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A common problem in graph colouring seeks to decompose the edge set of a given graph into few similar and simple subgraphs, under certain divisibility conditions. In 1987 Wormald conjectured that the edges of every cubic graph on $4n$ vertices can be partitioned into two isomorphic linear forests. We prove this conjecture for large connected cubic graphs. Our proof uses a wide range of probabilistic tools in conjunction with intricate structural analysis, and introduces a variety of local recolouring techniques. Comment: 49 pages, many figures |
| Databáze: | arXiv |
| Externí odkaz: |
|