Changes
Mulmuley, Vazirani and Vazirani <ref name="MuVaVa"/> showed that there is a randomized (RNC<sup>2</sup>) algorithm for the problem, based on computing a coefficient in the determinant of a matrix with indeterminates. This algorithm also works for non-bipartite graphs. Deterministic algorithms were given by Karzanov <ref name="Ka"/> for complete graphs and complete bipartite graphs. A simpler proof and a new algorithm for complete bipartite graphs were given by Yi, Murty and Spera <ref name="Yi"/>. Another simpler proof was given by Geerdes and Szabó <ref name="GeSz"/>.
For graphs which can be drawn to a fixed orientable surface Galluccio and Loebl <ref name="GaLo"/> gave a pseudo-polynomial algorithm using Pfaffian orientations, generalizing the analogous result of Barahona and Pulleyblank <ref name="BaPu"/> on planar graphs. Bhatnagar et al. <ref name="Bh"/> studied the problem of approximately counting the number of matchings with exactly ''k'' red edges. Yuster <ref name="Yu"/> gave a combinatorial polynomial algorithm that either certifies that no matching of size <math>\nu(G)</math> has exactly ''k'' red edges, or gives a matching of size <math>\nu(G)-1</math> containing exactly ''k'' red edges.
If the number of colours is not restricted and the graph is not necessarily simple, then the analogous problem is NP-complete: 3 dimensional perfect matching on ''3n'' nodes can be reduced to the problem of finding a multicoloured perfect matching in an ''n''-edge-coloured bipartite graph on ''2n'' nodes.
<references>
<ref name="MuVaVa">K. Mulmuley, U. V. Vazirani, V. V. Vazirani, ''Matching is as easy as matrix inversion'', Combinatorica 7 (1987), 105-113. [http://dx.doi.org/10.1007/BF02579206 DOI link]. [http://www.cs.berkeley.edu/~vazirani/pubs/matching.pdf Author link].</ref>
<ref name="Ka">A. V. Karzanov, ''On the maximal matchings of a given weight in complete and complete bipartite graphs'', Kibernetika 1 (1987), 7-11. (English translation in: Cybernetics and Systems Analysis 23 (1987), 8–13). [http://dx.doi.org/10.1007/BF01068796 DOI link.]</ref>
<ref name="Yi">T. Yi, K. G. Murty, C. Spera, ''Matchings in colored bipartite networks'', Discrete Applied Mathematics 121 (2002), 261-277. [http://dx.doi.org/10.1016/S0166-218X(01)00300-6 DOI link].</ref>
<ref name="GeSz">H.-F. Geerdes, J. Szabó. ''A unified proof for Karzanov's exact matching theorem'', [http://www.cs.elte.hu/egres/qp/egresqp-11-02.pdf EGRES Quick Proof No. 2011-02].</ref>
<ref name="GaLo">A. Galluccio, M. Loebl, ''On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents'', Electronic journal of combinatorics 6 (1999), R6. [http://www.emis.ams.org/journals/EJC/Volume_6/PDF/v6i1r6.pdf Pdf link.]</ref>
<ref name="BaPu">F. Barahona, W. R. Pulleyblank, ''Exact arborescences, matchings and cycles'', Discrete Appl. Math. 16 (1987) 91-99. [http://dx.doi.org/10.1016/0166-218X(87)90067-9 DOI link]</ref>
<ref name="Bh">N. Bhatnagar, D. Randall, V.V. Vazirani, E. Vigoda, ''Random Bichromatic Matchings'', Algorithmica 50 (2008), 418-445, [http://dx.doi.org/10.1007/s00453-007-9096-4 DOI link</ref> <ref name="Yu">R. Yuster, ''Almost exact matchings'', [http://dx.doi.org/10.1007/s00453-011-9519-0 DOI link], [http://research.haifa.ac.il/~raphy/papers/exactmatch.pdf author link]</ref>
<references/>
