Wormald's isomorphic linear-forest partition conjecture for cubic graphs

About 9 years old · traced to

Let GG be a cubic graph with an even number of edges. Equivalently, ∣V(G)∣|V(G)| is divisible by 44. A linear forest is a forest whose components are paths, and a linear partition is a partition of the edge set into linear forests.

Wormald's conjecture. There exists a linear partition of GG into two isomorphic linear forests.

This is equivalent to a 22-edge-colouring whose monochromatic subgraphs are isomorphic linear forests. The paper reports no counterexamples below 3232 vertices, but the conjecture remains open.

References

Primary source

Marien Abreu, Jan Goedgebeur, Domenico Labbate and Giuseppe Mazzuoccolo, “Colourings of cubic graphs inducing isomorphic monochromatic subgraphs”, arXiv:1705.06928 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.