Strong Ando conjecture for cubic graphs
Strong Ando conjecture for cubic graphs
Let be a cubic graph. A linear forest is a forest whose components are paths, and a bisection is a -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 , but the full conjecture remains open.
Sources & referencesView supporting material
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.