Colourings of cubic graphs inducing isomorphic monochromatic subgraphs. Issue 4 (9th May 2019) - Abreu, Marién; Goedgebeur, Jan; Labbate, Domenico; Mazzuoccolo, Giuseppe
Abstract: A k ‐bisection of a bridgeless cubic graph G is a 2 ‐colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes ( monochromatic components in what follows) have order at most k . Ban and Linial Conjectured that every bridgeless cubic graph admits a 2 ‐bisection except for the Petersen graph . A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph G with ∣ E ( G ) ∣ ≡ 0 ( mod 2 ) has a 2 ‐edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic . In this paper, we provide evidence of a strong relation of the conjectures of Ban‐Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above‐mentioned conjectures. Moreover, we prove Ban‐Linial's Conjecture for cubic‐cycle permutation graphs. As a by‐product of studying 2 ‐edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.