Kenjiro Takazawa - Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs

dmtcs:8719 - Discrete Mathematics & Theoretical Computer Science, March 31, 2022, vol. 24, no. 1 -
Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in DigraphsArticle

Authors: Kenjiro Takazawa

    An equitable partition into branchings in a digraph is a partition of the arc set into branchings such that the sizes of any two branchings differ at most by one. For a digraph whose arc set can be partitioned into $k$ branchings, there always exists an equitable partition into $k$ branchings. In this paper, we present two extensions of equitable partitions into branchings in digraphs: those into matching forests in mixed graphs; and into $b$-branchings in digraphs. For matching forests, Király and Yokoi (2022) considered a tricriteria equitability based on the sizes of the matching forest, and the matching and branching therein. In contrast to this, we introduce a single-criterion equitability based on the number of covered vertices, which is plausible in the light of the delta-matroid structure of matching forests. While the existence of this equitable partition can be derived from a lemma in Király and Yokoi, we present its direct and simpler proof. For $b$-branchings, we define an equitability notion based on the size of the $b$-branching and the indegrees of all vertices, and prove that an equitable partition always exists. We then derive the integer decomposition property of the associated polytopes.

    Volume: vol. 24, no. 1
    Section: Graph Theory
    Published on: March 31, 2022
    Accepted on: March 11, 2022
    Submitted on: November 18, 2021
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms

    Consultation statistics

    This page has been seen 751 times.
    This article's PDF has been downloaded 751 times.