{"docId":9275,"paperId":8719,"url":"https:\/\/dmtcs.episciences.org\/8719","doi":"10.46298\/dmtcs.8719","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":608,"name":"vol. 24, no. 1"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"2003.10774","repositoryVersion":4,"repositoryLink":"https:\/\/arxiv.org\/abs\/2003.10774v4","dateSubmitted":"2021-11-18 04:32:15","dateAccepted":"2022-03-11 09:37:37","datePublished":"2022-03-31 16:27:13","titles":["Notes on Equitable Partitions into Matching Forests in Mixed Graphs and\n into $b$-branchings in Digraphs"],"authors":["Takazawa, Kenjiro"],"abstracts":["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."],"keywords":["Mathematics - Combinatorics","Computer Science - Discrete Mathematics","Computer Science - Data Structures and Algorithms"]}