Coloured matchings in bipartite graphs (Q1357740)

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.