×

Badges and rainbow matchings. (English) Zbl 1462.05290

Summary: A. A. Drisko [J. Comb. Theory, Ser. A 84, No. 2, 181–195 (1998; Zbl 0915.05025)] proved that \(2 n - 1\) matchings of size \(n\) in a bipartite graph have a rainbow matching of size \(n\). For general graphs it is conjectured that \(2 n\) matchings suffice for this purpose (and that \(2 n - 1\) matchings suffice when \(n\) is even). The known graphs showing sharpness of this conjecture for \(n\) even are called badges. We improve the previously best known bound from \(3 n - 2\) to \(3 n - 3\), using a new line of proof that involves analysis of the appearance of badges. We also prove a “cooperative” generalization: for \(t > 0\) and \(n \geq 3\), any \(3 n - 4 + t\) sets of edges, the union of every \(t\) of which contains a matching of size \(n\), have a rainbow matching of size \(n\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0915.05025
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aharoni, R.; Berger, E., Rainbow matchings in \(r\)-partite \(r\)-graphs, Electron. J. Combin., 16, 1, 9 (2009), Research Paper 119 · Zbl 1186.05118
[2] Aharoni, R.; Berger, E.; Chudnovsky, M.; Howard, D.; Seymour, P., Large rainbow matchings in general graphs, European J. Combin., 79, 222-227 (2019) · Zbl 1414.05235
[3] Aharoni, R.; Berger, E.; Kotlar, D.; Ziv, R., Degree conditions for matchability in 3-partite hypergraphs, J. Graph Theory, 87, 1, 61-71 (2018) · Zbl 1380.05138
[4] Aharoni, R.; Holzman, R.; Jiang, Z., Rainbow fractional matchings, Combinatorica, 39, 1191-1202 (2019) · Zbl 1463.05532
[5] Aharoni, R.; Kotlar, D.; Ziv, R., Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv, European J. Combin., 67, 222-229 (2018) · Zbl 1371.05223
[6] Bárány, I., A generalization of Carathéodory’s theorem, Discrete Math., 40, 2-3, 141-152 (1982) · Zbl 0492.52005
[7] Barát, J.; Gyárfás, A.; Sárközy, G. N., Rainbow matchings in bipartite multigraphs, Period. Math. Hungar., 74, 1, 108-111 (2017) · Zbl 1399.05177
[8] Brualdi, R. A.; Ryser, H. J., (Combinatorial Matrix Theory. Combinatorial Matrix Theory, Encyclopedia of Mathematics and its Applications (1991), Cambridge University Press) · Zbl 0746.05002
[9] Drisko, A. A., Transversals in row-latin rectangles, J. Combin. Theory Ser. A, 84, 2, 181-195 (1998) · Zbl 0915.05025
[10] Holmsen, A.; Lee, S., Leray numbers of complexes of graphs with bounded matching number, arXiv:2003.11270 (2020), https://arxiv.org/abs/2003.11270
[11] Holmsen, A. F.; Pach, J.; Tverberg, H., Points surrounding the origin, Combinatorica, 28, 6, 633-644 (2008) · Zbl 1199.52013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.