Strong Ando conjecture for cubic graphs

About 9 years old · traced to

Let GG be a cubic graph. A linear forest is a forest whose components are paths, and a bisection is a 22-colouring of the vertex set with equally sized colour classes.

Strong Ando conjecture. Every cubic graph admits a bisection such that the two induced subgraphs are isomorphic linear forests.

This strengthens Ando's conjecture by requiring the common induced graph to be a linear forest. The paper notes that all known examples satisfy a bounded-component variant, with the Petersen graph requiring bound 44, but the full 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.