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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abreu, M., Goedgebeur, J., Labbate, D., Mazzuoccolo, G.: Colourings of cubic graphs inducing isomorphic monochromatic subgraphs. J. Graph. Theory 92, 415–444 (2019)
Abreu, M., Goedgebeur, J., Labbate, D., Mazzuoccolo, G.: A note on 2-bisections of claw-free cubic graphs. Discrete Appl. Math. 244, 214–217 (2018)
Ban, A., Linial, N.: Internal partitions of regular graphs. J. Graph. Theory 83, 5–18 (2016)
Cui, Q., Liu, W.: A note on 3-bisections in subcubic graphs. Discrete Appl. Math. 285, 147–152 (2020)
Cui, Q., Liu, Q.: \(2\)-bisections in claw-free cubic multigraphs. Discrete Appl. Math. 257, 325–330 (2019)
Esperet, L., Mazzuoccolo, G., Tarsi, M.: Flows and bisections in cubic graphs. J. Graph. Theory 86, 149–158 (2017)
Tarsi, M.: Bounded-excess flows in cubic graphs. J. Graph. Theory 95, 138–159 (2020)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Mattiolo, D., Mazzuoccolo, G. On 3-Bisections in Cubic and Subcubic Graphs. Graphs and Combinatorics 37, 743–746 (2021). https://doi.org/10.1007/s00373-021-02275-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-021-02275-z