On a generalization of the Ryser-Brualdi-Stein conjecture

DOI10.1002/JGT.21796MaRDI QIDQ2940993zbMATHOpenAlexWikidataFDO

Authors Ron Aharoni, Pierre Charbit, David M. Howard

Publication date 21 January 2015

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphmatchingsRyser's conjecturerainbow matchings

Mathematics Subject Classification ID

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

Abstract: A rainbow matching for (not necessarily distinct) sets F_1,...,F_k of hypergraph edges is a matching consisting of k edges, one from each F_i. The aim of the paper is twofold - to put order in the multitude of conjectures that relate to this concept (some of them first presented here), and to present some partial results on one of these conjectures, that seems central among them.

Recommendations

• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Multicolored matchings in hypergraphs
• On Rainbow Matchings for Hypergraphs
• Rainbow matchings and connectedness of coloured graphs
• On a conjecture of Stein

Cites work

• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A THEOREM ON INDEPENDENCE RELATIONS
• A weak version of Rota's bases conjecture for odd dimensions
• An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
• Combinatorial Matrix Theory
• Eigenvalues and homology of flag complexes and vector representations of graphs
• Hall's theorem for hypergraphs
• Large matchings in bipartite graphs have a rainbow matching
• On Representatives of Subsets
• On a list coloring conjecture of Reed
• On the relations of various conjectures on Latin squares and straightening coefficients
• Orthogonal Latin Rectangles
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Ryser's conjecture for tripartite 3-graphs
• The edge covering number of the intersection of two matroids
• The intersection of a matroid and a simplicial complex
• Transversals in row-latin rectangles
• Transversals of latin squares and their generalizations

Cited in

(22)

• Rainbow matchings in bipartite multigraphs
• Balanced diagonals in frequency squares
• A note on rainbow matchings in strongly edge-colored graphs
• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• Fair representation in the intersection of two matroids
• On a conjecture of Stein
• Longest partial transversals in plexes
• Full rainbow matchings in graphs and hypergraphs
• A survey on rainbow matchings in graphs and hypergraphs
• On acyclic edge-coloring of complete bipartite graphs
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• An approximate version of a conjecture of Aharoni and Berger
• Rainbow matchings and connectedness of coloured graphs
• Large matchings in bipartite graphs have a rainbow matching
• Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets
• Rainbow matchings and rainbow connectedness
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Existence of rainbow matchings in strongly edge-colored graphs
• Degree conditions for matchability in 3-partite hypergraphs
• Ramsey-nice families of graphs
• Representation of large matchings in bipartite graphs
• Multipartite hypergraphs achieving equality in Ryser's conjecture

This page was built for publication: On a generalization of the Ryser-Brualdi-Stein conjecture

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