Show simple item record

dc.contributor.authorCosta, Marie-Christine
dc.contributor.authorde Werra, Dominique
dc.contributor.authorPicouleau, Christophe
dc.contributor.authorRies, Bernard
dc.date.accessioned2020-05-22T14:40:49Z
dc.date.available2020-05-22T14:40:49Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20770
dc.language.isoenen
dc.subjectMatchingsen
dc.subjectAlternating cyclesen
dc.subjectBicolored graphsen
dc.subjectCactien
dc.subjectbipartite graphsen
dc.subjectLine-perfect graphsen
dc.subjecttreesen
dc.subject.ddc511en
dc.titleBicolored matchings in some classes of graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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 M k exist with |M k ∩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.en
dc.relation.isversionofjnlnameAKCE International Journal of Graphs and Combinatorics
dc.relation.isversionofjnlvol23en
dc.relation.isversionofjnldate2007-02
dc.relation.isversionofjnlpages47–60en
dc.relation.isversionofdoi10.1007/s00373-006-0686-8en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-05-22T14:38:38Z
hal.person.labIds
hal.person.labIds
hal.person.labIds
hal.person.labIds989


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record