Answers are grounded in this paper and cite their sources.
Given a multi-hypergraph G that is edge-colored into color classes E 1 , … , E n , a full rainbow matching is a matching of G that contains exactly one edge from each color class E i . One way to guarantee the existence of a full rainbow matching is to have the size of each color class E i be sufficiently large compared to the maximum degree of G . In this paper, we apply an iterative method to construct edge-colored multi-hypergraphs with a given maximum degree, large color classes, and no full rainbow matchings. First, for every r ≥ 1 and Δ ≥ 2 , we construct edge-colored r -uniform multi-hypergraphs with maximum degree Δ such that each color class has size | E i | ≥ r Δ − 1 and there is no full rainbow matching, which demonstrates that a theorem of Aharoni, Berger, and Meshulam (2005) is best possible. Second, we construct properly edge-colored multigraphs with no full rainbow matchings which disprove conjectures of Delcourt and Postle (2022). Finally, we apply results on full rainbow matchings to list edge-colorings and prove that a color degree generalization of Galvin’s theorem (1995) does not hold.
No takes yet. Share an insight, caveat, or question.
Ronen Wdowinski (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: