Bicolored matchings in some classes of graphs

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

Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2004), Bicolored matchings in some classes of graphs, AKCE International Journal of Graphs and Combinatorics, 23, p. 47–60. 10.1007/s00373-006-0686-8

Type

Article accepté pour publication ou publié

Date

2004

Journal name

AKCE International Journal of Graphs and Combinatorics

Volume

Pages

47–60

Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

Abstract (EN)

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

Subjects / Keywords

Matchings; Alternating cycles; Bicolored graphs; Cacti; bipartite graphs; Line-perfect graphs; trees