Formats
Format
BibTeX
MARC
MARCXML
DublinCore
EndNote
NLM
RefWorks
RIS

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