Notes on Equitable Partition into Matching Forests in Mixed Graphs and into b-branchings in Digraphs
share
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 (2018) 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 the covered vertices. For b-branchings, we define an equitability based on the size of the b-branching and the indegrees of all vertices. For both matching forests and b-branchings, we prove that equitable partitions always exist.
READ FULL TEXT