10.46298/dmtcs.8719
https://dmtcs.episciences.org/8719
Takazawa, Kenjiro
Kenjiro
Takazawa
Notes on Equitable Partitions into Matching Forests in Mixed Graphs and
into $b$-branchings in Digraphs
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\'{a}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\'{a}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.
episciences.org
Mathematics - Combinatorics
Computer Science - Discrete Mathematics
Computer Science - Data Structures and Algorithms
2022-03-11
2022-03-31
2022-03-31
eng
journal article
arXiv:2003.10774
10.48550/arXiv.2003.10774
1365-8050
https://dmtcs.episciences.org/8719/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 24, no. 1
Graph Theory
Researchers
Students