On 3-Bisections in Cubic and Subcubic Graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2021, Vol.37 (3), p.743-746
Main Authors: Mattiolo, Davide, Mazzuoccolo, Giuseppe
Format: Article
Language:English
Subjects:
Apexes
Combinatorics
Engineering Design
Graph theory
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-021-02275-z