Abstract

We consider the problem of finding in a graph a set $R$ of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with $n$ nodes on each side, we give sufficient conditions for the existence of a set $R$ with $|R| = n + 1$ such that perfect matchings with $k$ red edges exist for all $k, 0\le k\le n$. Given two integers $p

Details

Actions