Bicolored Matchings in Some Classes of Graphs

Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard

doi:10.1007/s00373-006-0686-8

Back

Journal article

Bicolored Matchings in Some Classes of Graphs

Costa, Marie-Christine CNAM, France
de Werra, Dominique EPFL, Switzerland
Picouleau, Christophe CNAM, France
Ries, Bernard EPFL, Switzerland

2007

Published in:

Graphs and Combinatorics. - 2007, vol. 23, no. 1, p. 47-60

Theoretical Computer Science

Discrete Mathematics and Combinatorics

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