Institution: Stanford University, Department of Computer Science

Title: Matroid partitioning.

Author: Knuth, Donald E.

Date: March 1973

Abstract: This report discusses a modified version of Edmonds's algorithm for partitioning of a set into subsets independent in various given matroids. If ${\cal M}_1$,...,${\cal M}_k$ are matroids defined on a finite set E, the algorithm yields a simple necessary and sufficient condition for whether or not the elements of E can be colored with k colors such that (i) all elements of color j are independent in ${\cal M}_j$, and (ii) the number of elements of color j lies between given limits, $n_j \leq \| E_j \| \leq {n'}_j$. The algorithm either finds such a coloring or it finds a proof that none exists, after making at most $n^3$ + $n^2$k tests of independence in the given matroids, where n is the number of elements in E.

http://i.stanford.edu/pub/cstr/reports/cs/tr/73/342/CS-TR-73-342.pdf