On a generalization of the Ryser-Brualdi-Stein conjecture

DOI10.1002/JGT.21796zbMATH Open1306.05187arXiv1305.6164OpenAlexW1805521509WikidataQ122890998 ScholiaQ122890998MaRDI QIDQ2940993FDOQ2940993

Authors: Ron Aharoni, Pierre Charbit, David M. Howard 

Publication date: 21 January 2015

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

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.

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

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

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)

Cites Work

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

Cited In (22)

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

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)