{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T08:38:08Z","timestamp":1768293488325,"version":"3.49.0"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2021,1,20]],"date-time":"2021-01-20T00:00:00Z","timestamp":1611100800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>G<\/jats:italic> be a simple graph that is properly edge-coloured with <jats:italic>m<\/jats:italic> colours and let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000620_inline1.png\"\/><jats:tex-math>\\[\\mathcal{M} = \\{ {M_1},...,{M_m}\\} \\]<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be the set of <jats:italic>m<\/jats:italic> matchings induced by the colours in <jats:italic>G<\/jats:italic>. Suppose that <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000620_inline2.png\"\/><jats:tex-math>\\[m \\leqslant n - {n^c}\\]<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000620_inline3.png\"\/><jats:tex-math>\\[c &gt; 9\/10\\]<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and every matching in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000620_inline4.png\"\/><jats:tex-math>\\[\\mathcal{M}\\]<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> has size <jats:italic>n<\/jats:italic>. Then <jats:italic>G<\/jats:italic> contains a full rainbow matching, <jats:italic>i.e.<\/jats:italic> a matching that contains exactly one edge from <jats:italic>M<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> for each <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000620_inline5.png\"\/><jats:tex-math>\\[1 \\leqslant i \\leqslant m\\]<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalization of a special case of a conjecture of Aharoni and Berger. Related results are also found for multigraphs with edges of bounded multiplicity, and for hypergraphs.<\/jats:p><jats:p>Finally, we provide counterexamples to several conjectures on full rainbow matchings made by Aharoni and Berger.<\/jats:p>","DOI":"10.1017\/s0963548320000620","type":"journal-article","created":{"date-parts":[[2021,1,20]],"date-time":"2021-01-20T11:13:23Z","timestamp":1611141203000},"page":"762-780","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Full rainbow matchings in graphs and hypergraphs"],"prefix":"10.1017","volume":"30","author":[{"given":"Pu","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reshma","family":"Ramadurai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian M.","family":"Wanless","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nick","family":"Wormald","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,1,20]]},"reference":[{"key":"S0963548320000620_ref18","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548320000620_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301005089"},{"key":"S0963548320000620_ref12","doi-asserted-by":"publisher","DOI":"10.37236\/6481"},{"key":"S0963548320000620_ref20","doi-asserted-by":"publisher","DOI":"10.1137\/17M1151742"},{"key":"S0963548320000620_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000274"},{"key":"S0963548320000620_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.01.002"},{"key":"S0963548320000620_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030102"},{"key":"S0963548320000620_ref1","doi-asserted-by":"publisher","DOI":"10.37236\/208"},{"key":"S0963548320000620_ref2","unstructured":"[2] Aharoni, R. , Berger, E. , Chudnovsky, M. , Howard, D. and Seymour, P. (2016) Large rainbow matchings in general graphs. arXiv:1611.03648v3"},{"key":"S0963548320000620_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008590"},{"key":"S0963548320000620_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.05.036"},{"key":"S0963548320000620_ref27","unstructured":"[27] Ryser, H. (1967) Neuere Probleme der Kombinatorik. In Vortr\u00e4ge \u00fcber Kombinatorik, Oberwolfach, pp. 69\u201391."},{"key":"S0963548320000620_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139004114.010"},{"key":"S0963548320000620_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21796"},{"key":"S0963548320000620_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S0963548320000620_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.11.011"},{"key":"S0963548320000620_ref10","first-page":"211","article-title":"Rainbow matchings and transversals","volume":"59","author":"Bar\u00e1t","year":"2014","journal-title":"Australas. J. Combin"},{"key":"S0963548320000620_ref8","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"S0963548320000620_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10998-016-0172-x"},{"key":"S0963548320000620_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.01.012"},{"key":"S0963548320000620_ref28","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1975.59.567"},{"key":"S0963548320000620_ref24","doi-asserted-by":"publisher","DOI":"10.1112\/plms.12245"},{"key":"S0963548320000620_ref13","doi-asserted-by":"publisher","DOI":"10.37236\/5080"},{"key":"S0963548320000620_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.21566"},{"key":"S0963548320000620_ref15","unstructured":"[15] Gao, P. , Ramadurai, R. , Wanless, I. M. and Wormald, N. (2017) Counterexamples on matchings in hypergraphs and full rainbow matchings in graphs. arXiv:1710.04807"},{"key":"S0963548320000620_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/16M1062958"},{"key":"S0963548320000620_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"S0963548320000620_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548319000282"},{"key":"S0963548320000620_ref25","doi-asserted-by":"publisher","DOI":"10.37236\/5246"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000620","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,6]],"date-time":"2021-08-06T13:35:57Z","timestamp":1628256957000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000620\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,20]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["S0963548320000620"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000620","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,20]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}