Bicolored Matchings in Some Classes of Graphs |
| |
Authors: | M. C. Costa D. de Werra C. Picouleau B. Ries |
| |
Affiliation: | (1) CEDRIC, CNAM, Paris;(2) IMA - EPFL, Lausanne |
| |
Abstract: | 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 matchings Mk 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. |
| |
Keywords: | Matchings Alternating cycles Bicolored graphs Cacti bipartite graphs Line-perfect graphs trees |
本文献已被 SpringerLink 等数据库收录! |