A k-bisection of a graph is a partition of the vertices in two classes whose cardinalities differ of at most one and such that the subgraphs induced by each class are acyclic with all connected components of order at most k. Esperet, Tarsi and the second author proved in 2017 that every simple cubic graph admits a 3-bisection. Recently, Cui and Liu extended that result to the class of simple subcubic graphs. Their proof is an adaptation of the quite long proof of the cubic case to the subcubic one. Here, we propose an easier proof of a slightly stronger result. Indeed, starting from the result for simple cubic graphs, we prove the existence of a 3-bisection for all cubic graphs (also admitting parallel edges). Then we prove the same result for the larger class of subcubic graphs as an easy corollary.

On 3-Bisections in Cubic and Subcubic Graphs / Mattiolo, Davide; Mazzuoccolo, Giuseppe. - In: GRAPHS AND COMBINATORICS. - ISSN 0911-0119. - (2021), pp. 1-4. [10.1007/s00373-021-02275-z]

### On 3-Bisections in Cubic and Subcubic Graphs

#### Abstract

A k-bisection of a graph is a partition of the vertices in two classes whose cardinalities differ of at most one and such that the subgraphs induced by each class are acyclic with all connected components of order at most k. Esperet, Tarsi and the second author proved in 2017 that every simple cubic graph admits a 3-bisection. Recently, Cui and Liu extended that result to the class of simple subcubic graphs. Their proof is an adaptation of the quite long proof of the cubic case to the subcubic one. Here, we propose an easier proof of a slightly stronger result. Indeed, starting from the result for simple cubic graphs, we prove the existence of a 3-bisection for all cubic graphs (also admitting parallel edges). Then we prove the same result for the larger class of subcubic graphs as an easy corollary.
##### Scheda breve Scheda completa Scheda completa (DC)
2021
1
4
On 3-Bisections in Cubic and Subcubic Graphs / Mattiolo, Davide; Mazzuoccolo, Giuseppe. - In: GRAPHS AND COMBINATORICS. - ISSN 0911-0119. - (2021), pp. 1-4. [10.1007/s00373-021-02275-z]
Mattiolo, Davide; Mazzuoccolo, Giuseppe
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### 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

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1310843`
• ND
• 1
• 1