๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Coloured matchings in bipartite graphs

โœ Scribed by Kathie Cameron

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
213 KB
Volume
169
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A theorem of states that for every n x n (n ~> 3) complete bipartite graph G such that every edge is coloured and each colour is the colour of at most two edges, there is a perfect matching whose edges have distinct colours. We give an O(n 2) algorithm for finding such a perfect matching. We show that a related problem is NP-complete.

๐Ÿ“œ SIMILAR VOLUMES

Induced matchings in bipartite graphs
Induced matchings in bipartite graphs
โœ R.J. Faudree; A. Gyรกrfas; R.H. Schelp; Zs. Tuza ๐Ÿ“‚ Article ๐Ÿ“… 1989 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 454 KB
Special parity of perfect matchings in b
Special parity of perfect matchings in bipartite graphs
โœ Ron Aharoni; Rachel Manber; Bronislaw Wajnryb ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 527 KB

Let G be a bipartite graph in which every edge belongs to some perfect matching, and let D be a subset of its edge set. It is shown that M fl D has the same parity for every perfect matching M if and only if D is a cut, and equivalently if and only. if (G, D) is a balanced signed-graph. This gives n

Perfect matchings and ears in elementary
Perfect matchings and ears in elementary bipartite graphs
โœ Pierre Hansen; Fuji Zhang; Maolin Zheng ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 386 KB

We give lower and upper bounds for the number of reducible ears as well as upper bounds for the number of perfect matchings in an elementary bipartite graph. An application to chemical graphs is also discussed. In addition, a method to construct all minimal elementary bipartite graphs is described.