Costa, Marie-Christinede Werra, DominiquePicouleau, ChristopheRies, Bernard2006-08-312006-08-312006-08-31200710.1007/s00373-006-0686-8https://infoscience.epfl.ch/handle/20.500.14299/233945WOS:00024444770000210183We 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<q$ we also determine the minimum cardinality of a set $R$ of red edges such that there are perfect matchings with $p$ red edges and with $q$ red edges. For 3-regular bipartite graphs, we show that if $p\le 4$ there is a set $R$ with $|R| = p$ for which perfect matchings $M_k$ exist with $\vert M_k\cap R\vert\le k$ for all $k\le p$. For trees we design a linear time algorithm to determine a minimum set $R$ of red edges such that there exist maximum matchings with $k$ red edges for the largest possible number of values of $k$.matchingsalternating cyclesbicolored graphscactibipartite graphsline-perfect graphstreestext::journal::journal article::research article