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. - 37:3(2021), pp. 743-746. [10.1007/s00373-021-02275-z]

On 3-Bisections in Cubic and Subcubic Graphs

Davide Mattiolo;Giuseppe Mazzuoccolo
2021

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.
2021
37
3
743
746
On 3-Bisections in Cubic and Subcubic Graphs / Mattiolo, Davide; Mazzuoccolo, Giuseppe. - In: GRAPHS AND COMBINATORICS. - ISSN 0911-0119. - 37:3(2021), pp. 743-746. [10.1007/s00373-021-02275-z]
Mattiolo, Davide; Mazzuoccolo, Giuseppe
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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/1310843
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact