Coloured matchings in bipartite graphs (Q1357740): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3348434 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some Matching Problems for Bipartite Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transversals of latin squares and their generalizations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Splitting groups of prime order / rank | |||
Normal rank |
Latest revision as of 16:41, 27 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Coloured matchings in bipartite graphs |
scientific article |
Statements
Coloured matchings in bipartite graphs (English)
0 references
1997
0 references
Let \(G\) be a complete bipartite \(n\times n\) \((n\geq 3)\) graph such that every edge is coloured and each colour is the colour of at most two edges. Stein's theorem asserts there is a good perfect matching in \(G\). The author shows that if \(M\) is a good matching in \(G\) which does not hit vertices \(r\) and \(s\), respectively, in the two parts of \(G\), and \(|M|\geq 2\), then there is a good augmenting path from \(r\) to \(s\) with at most 5 edges. The proof of this result actually provides an \(O(n^2)\) algorithm for finding a good perfect matching. A related problem is shown to be NP-complete, too.
0 references
bipartite graphs
0 references
good perfect matching
0 references
algorithm
0 references
NP-complete
0 references