Pokrovskiy, A;
(2015)
Rainbow matchings and connectedness of coloured graphs.
Electronic Notes in Discrete Mathematics
, 49
pp. 371-376.
10.1016/j.endm.2015.06.052.
Preview |
Text
RainbowAbstract.pdf - Accepted Version Download (198kB) | Preview |
Abstract
Aharoni and Berger conjectured that every bipartite graph which is the union of n matchings of size n + 1 contains a rainbow matching of size n. This conjecture is a generalization of several old conjectures of Ryser, Brualdi, and Stein about transversals in Latin squares. When the matchings are all edge-disjoint and perfect, an approximate version of this conjecture follows from a theorem of Häggkvist and Johansson which implies the conjecture when the matchings have size at least n + o(n).Here we'll discuss a proof of this conjecture in the case when the matchings have size n + o(n) and are all edge-disjoint (but not necessarily perfect). The proof involves studying connectedness in coloured, directed graphs. The notion of connectedness that we introduce is new, and perhaps of independent interest.
| Type: | Article |
|---|---|
| Title: | Rainbow matchings and connectedness of coloured graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.endm.2015.06.052 |
| Publisher version: | https://doi.org/10.1016/j.endm.2015.06.052 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Latin squares, connectedness, transversals, matchings |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10112663 |
Archive Staff Only
 |
View Item |
