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
Davide Mattiolo;Giuseppe Mazzuoccolo
2021-01-01
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
