Costa, Marie-Christine de Werra, Dominique Picouleau, Christophe Ries, Bernard 2007 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 ≤ k ≤ 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 ≤ 4 there is a set R with |R| = p for which perfect matchingsMk exist with |Mk ∩R| ≤ k for all k ≤ 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. application/pdf https://folia.unifr.ch/global/documents/307835 https://folia.unifr.ch/documents/307835/files/bicoloredmatchingscopy.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1007/s00373-006-0686-8 info:eu-repo/semantics/openAccess License undefined Graphs and Combinatorics. - 2007, vol. 23, no. 1, p. 47-60 Theoretical Computer Science Discrete Mathematics and Combinatorics info:eu-repo/classification/udc/004 Bicolored Matchings in Some Classes of Graphs http://purl.org/coar/resource_type/c_6501