59 problems

Ryser–Brualdi–Stein conjecture. Any proper edge-coloring of $K_{n,n}$ using $n$ colors contains a rainbow matching of size $n-1$, with a rainbow matching of size $n$ existing whene…

For a positive integer $n$, write $[n]=\{1,\ldots,n\}$, and let $\binom{[n]}{k}$ be the family of $k$-subsets of $[n]$. Let $\mathcal F=\{F_1,\ldots,F_t\}$ be a family of subsets o…

A rainbow matching is a matching whose edges have pairwise distinct colors. Grinblat's conjecture. If $G$ is a multigraph that is not necessarily properly edge colored with $n$ col…

Let $\binom{[n]}{k}$ denote the family of $k$-subsets of $[n]$. Rainbow Erdős Matching Conjecture. If $n\geq(s+1)k$ and…

Let $G$ be a multigraph, and let $E_1,\ldots,E_n$ be color classes of a proper edge-coloring of $G$. A full rainbow matching is a matching containing exactly one edge from each col…

A $2$-factor is a spanning $2$-regular subgraph, and a full rainbow matching is a matching containing one edge from every color class. Alspach's conjecture. If $G$ is a simple $2d$…

Let $n$ be a positive integer, and let $M_1,\ldots,M_{2n}$ be matchings of size $n$ in a graph; the matchings need not be disjoint, and the graph is not assumed to be bipartite. A…

Let $n$ be a positive integer, and let $G$ be a graph. A rainbow matching for a family of matchings is a matching whose edges can be injectively assigned to distinct members of the…

Degree-bounded bipartite rainbow matching conjecture. If

Let $G$ be a graph with an edge coloring $\phi$, let $r(G,\phi)$ be the size of a largest rainbow matching in $G$, and let $\hat{\delta}(G,\phi)$ be the minimum color degree of $G$…

Let $n,k,M\in\mathbb{N}$ with $M\ge nk$. If … are cross-dependent, meaning that there are no pairwise disjoint choices $F_j\in\mathcal F_j$ for $j\in[n]$, then Rainbow Erdős matchi…

Let $G$ be a strongly edge-colored graph on $n$ vertices, and let $\delta$ denote its minimum degree. Wang, Yan and Yu's conjecture. If … then $G$ has a rainbow matching of size…

Let $G$ be a bipartite graph, and let $M_1,\ldots,M_n$ be matchings in $G$, each of size $n$. A partial rainbow matching is a matching containing at most one edge from each $M_i$.…

Let $s,n,k$ be positive integers, and let a sequence $(f_i)_{i=1}^s$ be called satisfying when it has the property that any $s$ families in $[n]^k$ whose respective sizes exceed…

Aharoni-Berger-Chudnovsky-Zerbib conjecture.

Let $K_{n,n}$ be a complete bipartite graph with a proper edge-colouring, meaning that no two edges of the same colour meet at a vertex. A rainbow matching is a matching whose edge…

Let $G$ be a multigraph with maximum degree $\Delta$, and let $E_1,\ldots,E_n$ be color classes of a proper edge-coloring of $G$. A full rainbow matching is a matching containing e…

Let $\mathcal{G}=\{G_1,\ldots,G_t\}$ be a family of $t$ bipartite graphs, and let $\Delta$ be a bound such that $\Delta(G_i)\leq \Delta$ for every $i$. Aharoni and Howard's rainbow…

Let $G$ be a multigraph whose edges are $t$-coloured, with each colour class a matching of size at least $t+20t^{15/16}$. Gao–Ramadurai–Wanless–Wormald conjecture. The conclusion o…

Pinnable rainbow matching conjecture. If

A properly edge-colored bipartite simple graph is a bipartite simple graph in which incident edges have distinct colors; a rainbow matching is a matching whose edges have pairwise…

Let $[n]=\{1,2,\dots,n\}$ and let $\binom{[n]}{k}$ denote the collection of all $k$-subsets of $[n]$. Let $\mathcal{F}_1,\mathcal{F}_2,\dots,\mathcal{F}_s\subseteq\binom{[n]}{k}$.…

Rödl–Ruciński–Szemerédi conjecture. This threshold function is

Let $G$ be an edge-coloured multigraph with $n$ colours such that each colour class is a matching of size $n+2$. A rainbow matching is a matching containing at most one edge of eac…

Let $G$ be an edge-colored graph, let $\hat d(G)$ be its average color degree, and let $\widetilde{K_4}$ denote the exceptional edge-colored graph referred to in the source. A rain…