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.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
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