Bicolored Matchings in Some Classes of Graphs
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.
-
Faculty
- Faculté des sciences économiques et sociales et du management
-
Department
- Département d'informatique
-
Language
-
-
Classification
-
Computer science and technology
-
License
-
License undefined
-
Identifiers
-
-
Persistent URL
-
https://folia.unifr.ch/unifr/documents/307835
Statistics
Document views: 38
File downloads:
- bicoloredmatchingscopy.pdf: 115