information:highlighting, information:filtering
Rainbow fractional matchings

A fractional matching is a set of edges with a non-negative weight assigned to each edge, such that the sum of weights adjacent to each vertex is at most 1. The size of a fractional matching is the sum of weights of all edges. It is a generalization of a matching, and can be used to generalize both the colors and the rainbow matching:

It is known that, in a bipartite graph, the maximum fractional matching size equals the maximum matching size. Therefore, the theorem of Aharoni and Berger is equivalent to the following. Let n be any positive integer. Given any family of 2 n – 1 fractional-matchings (=colors) of size n in a bipartite graph, there exists a rainbow-fractional-matching of size n.

Aharoni, Holzman and Jiang extend this theorem to arbitrary graphs as follows. Let n be any positive integer or half-integer. Any family of 2 n fractional-matchings (=colors) of size at least n in an arbitrary graph has a rainbow-fractional-matching of size n. The 2 n is the smallest possible for fractional matchings in arbitrary graphs: the extremal case is constructed using an odd-length cycle.