Coloured matchings in bipartite graphs (Q1357740): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q587976 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Jozef Fiamčik / rank | |||
Normal rank |
Revision as of 12:20, 16 February 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