论文标题
将立方图分解成同构线性森林
Decomposing cubic graphs into isomorphic linear forests
论文作者
论文摘要
图形着色中的一个常见问题旨在将给定图的边缘集分解为某些分裂条件下的几个相似和简单的子图。 1987年，蠕虫猜想，$ 4N $顶点的每个立方图的边缘可以分为两个同构线性森林。我们证明了大型连接的立方图的猜想。我们的证明与复杂的结构分析结合使用了广泛的概率工具，并引入了各种本地重新塑造技术。
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.
