Bicolored matchings in some classes of graphs
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
2004Journal name
AKCE International Journal of Graphs and CombinatoricsVolume
23Pages
47–60
Publication identifier
Metadata
Show full item recordAuthor(s)
Costa, Marie-Christinede Werra, Dominique
Picouleau, Christophe

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 pSubjects / Keywords
Matchings; Alternating cycles; Bicolored graphs; Cacti; bipartite graphs; Line-perfect graphs; trees
Related items
Showing items related by title and author.
-
Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
-
Ries, Bernard; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2011) Chapitre d'ouvrage
-
de Werra, Dominique; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard (2010) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié
-
Bernard Ries; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2009) Article accepté pour publication ou publié