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)| equivalent to O (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.

Colourings of cubic graphs inducing isomorphic monochromatic subgraphs / Abreu, Marién; Goedgebeur, Jan; Labbate, Domenico; Mazzuoccolo, Giuseppe. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 92:4(2019), pp. 415-444. [10.1002/jgt.22462]

Colourings of cubic graphs inducing isomorphic monochromatic subgraphs

Mazzuoccolo, Giuseppe
2019

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)| equivalent to O (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.
2019
92
4
415
444
Colourings of cubic graphs inducing isomorphic monochromatic subgraphs / Abreu, Marién; Goedgebeur, Jan; Labbate, Domenico; Mazzuoccolo, Giuseppe. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 92:4(2019), pp. 415-444. [10.1002/jgt.22462]
Abreu, Marién; Goedgebeur, Jan; Labbate, Domenico; Mazzuoccolo, Giuseppe
File in questo prodotto:
File Dimensione Formato  
bcol_permgraphs_2018-09-05_rev_giuseppe.pdf

Accesso riservato

Dimensione 548.04 kB
Formato Adobe PDF
548.04 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1310853
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact