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.
- The labeled perfect matching in bipartite graphs
- Matchings in colored bipartite networks
- Bottleneck subset-type restricted matching problems
- Algorithms and complexity for a class of combinatorial optimization problems with labelling
- Role coloring bipartite graphs
- Matchings with few colors in colored complete graphs and hypergraphs
- Maximum weight edge-constrained matchings
- scientific article; zbMATH DE number 5914945 (Why is no real title available?)
- Random Bichromatic Matchings
- A note on the hardness results for the labeled perfect matching problems in bipartite graphs
- A weighted perfect matching with constraints on weights of its parts
- Augmenting trail theorem for the maximum 1-2 matching problem
- Bicolored matchings in some classes of graphs
- Minimum <scp>color‐degree</scp> perfect b‐matchings
- Three results towards approximation of special maximum matchings in graphs
- Maximum transversal in partial Latin squares and rainbow matchings
- On complexity of special maximum matchings constructing
This page was built for publication: Coloured matchings in bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1357740)
