Colorability of induced matroids Original Research Article

Let G be a bipartite graph with bipartition {X, Y} such that there is a matching which matches Y with a subset of X. Let image be a matroid on X, and for each positive integer k, let image(k) be the matroid on X which is the union of image with itself k times. The G-induced chromatic number of image is the smallest integer p such that Y is an independent set of the induced matroid (image(p))G. This chromatic number gives rise to a partition of Y called the G-induced chromatic partition. This partition majorizes partitions corresponding to other induced partitions, of Y.