Badges and rainbow matchings

DOI10.1016/J.DISC.2021.112363MaRDI QIDQ2022150zbMATH OpenOpenAlexFDO

Authors Joseph Briggs, Jinha Kim, Ron Aharoni, Min-Ki Kim

Publication date 28 April 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.07590

zbMATH Keywords

badgesmatchingsrainbow matchings

Mathematics Subject Classification ID

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

Abstract: Drisko proved that $2n-1$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n$. For general graphs it is conjectured that $2n$ matchings suffice for this purpose (and that $2n-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 $3n-2$ to $3n-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 $ngeq3$, any $3n-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$.

Recommendations

• Large rainbow matchings in general graphs
• On rainbow matchings in bipartite graphs
• Rainbow paths and large rainbow matchings
• Rainbow matchings in bipartite multigraphs
• An improved bound on the sizes of matchings guaranteeing a rainbow matching

Cites work

• A generalization of Caratheodory's theorem
• Combinatorial matrix theory
• Degree conditions for matchability in 3-partite hypergraphs
• Large rainbow matchings in general graphs
• Points surrounding the origin
• Rainbow fractional matchings
• Rainbow matchings in r-partite r-graphs
• Rainbow matchings in bipartite multigraphs
• Transversals in row-latin rectangles
• Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv

Cited in

(8)

• Rainbow paths and large rainbow matchings
• Leray numbers of complexes of graphs with bounded matching number
• Rainbow independent sets in graphs with maximum degree two
• A system of disjoint representatives of line segments with given \(k\) directions
• Rainbow independent sets in certain classes of graphs
• Choice functions
• Keep your distance: land division with separation
• Rainbow independent sets on dense graph classes

This page was built for publication: Badges and rainbow matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022150)