45 problems

Let $F_i$, $i\leq k$, be subgraphs of $K_{n,n}$, and let $A=(a_{ij})$ be the $k\times n$ matrix whose entry $a_{ij}$ is the degree of $v_j$ in $F_i$. Let $r_i(A)$ be the sum of the…

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…

Asymptotic rainbow matching conjecture. Fix $r\geq2$. For every $x\in\{g(r,n),g'(r,n),h(r,n),h'(r,n)\}$,

Aharoni-Berger non-bipartite strong conjecture. Every collection of $n$ matchings of size $n+2$ in a graph admits a rainbow matching of size $n$.

Aharoni-Berger strong conjecture. Every collection of $n$ matchings of size $n+1$ in a bipartite graph admits a rainbow matching of size $n$.

Aharoni-Berger conjecture. Every collection of $n$ matchings of size $n$ in a graph admits a rainbow matching of size $n-1$.

Ryser–Brualdi–Stein conjecture. Every such coloring contains a rainbow matching of size $n-1$; moreover, if $n$ is odd, it contains a perfect rainbow matching.

Let $K_n$ be the complete graph on $n$ vertices, and let a proper edge-colouring be an edge-colouring in which edges of the same colour do not meet. A rainbow path is a path whose…

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…

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…

Pinnable rainbow matching conjecture. If

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…

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]=\{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}$.…

An $(n,v)$-multigraph is an $n$-edge-coloured multigraph in which the edges of each colour span a disjoint union of non-trivial cliques whose total number of vertices is at least…

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…

Barát–Gyárfás–Sárközy conjecture. Then $G$ has a rainbow matching using $n$ colors.

Brualdi–Ryser–Stein conjecture. Every $n\times n$ Latin square has a partial transversal of size $n-1$.

Let $\textsc{bm}(a_1,a_2,t)$ denote the balanced matching parameter for the indicated complete bipartite setting. Tightness conjecture. For every integer $n\geq4$, … This would mak…

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…

Let $(m,n)\to k$ mean that every $m$ matchings of size $n$ in any graph have a rainbow matching of size $k$. Rainbow matching conjecture. … The conjecture is stated as a general-gr…

Let $(m,n)\to k$ mean that every $m$ matchings of size $n$ in any graph have a rainbow matching of size $k$. The notation $(m,n)\to_{\mathcal{B}} k$ has the same meaning for bipart…