Colourings of cubic graphs inducing isomorphic monochromatic subgraphs. Issue 4 (9th May 2019)

• Record Type: Journal Article
• Authors: Abreu, Marién; Goedgebeur, Jan; Labbate, Domenico; Mazzuoccolo, Giuseppe
• Is Part Of: Journal of graph theory. Volume 92:Issue 4(2019)
• Page Start: 415
• Page End: 444
• Publication Date: 2019-05-09
• Subjects: bisection -- colouring -- computation -- cubic graph -- cycle permutation graph -- linear forest -- snark; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22462
• Languages: English
• ISSNs: 0364-9024

Abstract

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.