A note on 3-bisections in subcubic graphs

Abstract A k -bisection of a graph G is a partition of its vertex set into two sets V 1 and V 2 such that | | V 1 | − | V 2 | | ≤ 1 and every connected component of G [ V i ] has at most k vertices, where G [ V i ] denotes the subgraph of G induced by V i ( i = 1 , 2 ). A subcubic graph is a graph with maximum degree at most three. In this note, we prove that every subcubic graph G admits a 3-bisection ( V 1 , V 2 ) with an additional property that every connected component of G [ V i ] ( i = 1 , 2 ) is acyclic. This extends a recent result of Esperet, Mazzuoccolo and Tarsi who showed that every cubic graph admits such a 3-bisection.