Journal article

Bicolored Matchings in Some Classes of Graphs

Show more…
Published in:
  • Graphs and Combinatorics. - 2007, vol. 23, no. 1, p. 47-60
English 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.
Faculté des sciences économiques et sociales
Département d'informatique
  • English
Computer science
License undefined
Persistent URL

Document views: 7 File downloads:
  • bicoloredmatchingscopy.pdf: 1