Bicolored Matchings in Some Classes of Graphs
Published in:
 Graphs and Combinatorics.  2007, vol. 23, no. 1, p. 4760
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 3regular 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.

Faculty
 Faculté des sciences économiques et sociales

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/307835
Statistics
Document views: 7
File downloads:
 bicoloredmatchingscopy.pdf: 1