159 problems

Ryser's conjecture. The size of a minimum vertex cover of $H$ is at most $r-1$ times the size of a maximum matching of $H$.

Let $n$ be even. In the rainbow perfect matching game $\mathcal{RP}_n$, played on $n/2$ copies of $K_n$, Maker wins by claiming a rainbow perfect matching; let $b_{\mathcal{RP}_n}$…

Let $H$ be an $r$-partite hypergraph containing at least one edge, and let $\nu(H)$ denote its matching number, the maximum number of pairwise disjoint edges. For a set $S$ of vert…

Let $n$, $k$, and $D$ be integers with $2D\mid n$. A $D$-regular graph is a graph on $n$ vertices in which every vertex has degree $D$, and a matching of size $k$ is a set of $k$ p…

Rohatgi's conjecture. The lower bound is tight:

The $n$-dimensional hypercube $Q_n$ has as vertices all subsets of $[n]:=\{1,\ldots,n\}$, with edges joining sets that differ in a single element. A matching is a set of pairwise v…

Let $k\geq 3$ and let $G$ be a $k$-critical graph. Let $\mu(G)$ denote the matching number and $\mu_f(G)$ the fractional matching number. Fractional matching gap conjecture. If $G$…

Let $\mathcal{H}$ be an $r$-uniform hypergraph on $n$ vertices, and let $\nu(\mathcal{H})$ denote its matching number. Define $\mathcal{H}_1$ as the hypergraph consisting of all…

Let $n=s(m+1)-\ell$ and define … For $s\ge2$, $m\ge1$, and $1\le\ell\le\lceil s/2\rceil$, this family is a weighted construction with matching number less than $s$. Frankl–Kupavski…

Let $Q_n$ be the graph whose vertices are the subsets of $[n]:=\{1,\ldots,n\}$, with edges joining sets that differ in a single element. A matching is a set of pairwise vertex-disj…

Interval-chromatic-two conjecture. There exists an $\epsilon>0$ such that, for every ordered matching $M^<$ on $n$ vertices with $\chi_<(M^<)=2$,

Let $T$ be a tree with a perfect matching. An adding-edge-subtracting dual graph transformation replaces an edge $u_{k-1}v_{k-1}\in E(H_{k-1})$ by an edge $x_ky_k\notin E(H_{k-1})$…

Let $Q_d$ be the $d$-dimensional hypercube, and let $varphi$ be a partial $d$-edge coloring of $Q_d$. A color class is the set of edges receiving one fixed color, and an induced ma…

Let $G$ be a $d$-regular graph, and let $M_G(\lambda)=\sum_k m_k(G)\lambda^k$ be its matching partition function, where $m_k(G)$ is the number of matchings of size $k$. Write…

Let $G$ be a connected graph of order $n(G)$ and maximum degree at most $3$, with girth at least $5$. A matching $M$ in $G$ is uniquely restricted if no other matching in $G$ cover…

Let $n$ be a positive integer and let $\pi,\sigma,\lambda\vdash n$ be partitions. Let $\mathcal{G}^{\lambda}_{\pi,\sigma}$ denote the set of matchings $\delta$ satisfying…

Goldberg's conjecture. If $G$ is an edge-$k$-critical graph with $k\geq\Delta+1$, then, for every $e\in E(G)$, the edge set $E(G)-e$ can be partitioned into disjoint near-perfect m…

Let $G$ be a $d$-regular graph on $n$ vertices, and let $H_{d,n}$ be the graph consisting of $n/(2d)$ copies of $K_{d,d}$. For each integer $k$ with $1\le k\le n/2$, write $m_k(G)$…

Write $n=sm+c=s(m+1)-\ell$, and for $0\le k\le m$ define … and let $\mathcal P(m,s,\ell)$ be the shifted family $\{F\subseteq[n]\colon |F|+|F\cap[\ell-1]|\ge m+1\}$. Completeness c…

Write $n=sm+c=s(m+1)-\ell$, and for $0\le k\le m$ let $a_k=ms-kc-1$. For $A\in\binom{[n]}{a_k}$, define … and let $\mathcal H^k(m,s,\ell)=\mathcal H^k(m,s,\ell;[a_k])$. Also let…

Let $[n]=\{1,2,\ldots,n\}$, let $e(n,s)$ be the maximum of $|\mathcal F|$ over families $\mathcal F\subseteq 2^{[n]}$ with matching number $\nu(\mathcal F)<s$, and, for a weight fu…

Let $T$ be a tournament, namely an oriented graph in which every pair of distinct vertices is joined by exactly one directed arc. For a vertex $x$, let $N_T^+(x)$ and $N_T^{++}(x)$…

Let $D$ be an oriented graph. For a vertex $x$, let $N_D^+(x)$ and $N_D^{++}(x)$ denote its out-neighborhood and second out-neighborhood, respectively. A complete matching from $X$…

Type $(4,3)$ finite asymptotic separation index matching conjecture. If $\mathsf{asi}(G)<\infty$, then $G$ has a Borel matching covering $A$.

Finite asymptotic separation index matching conjecture. If the bipartition has combinatorial expansion and $\mathsf{asi}(G)<\infty$, then $G$ has a Borel matching covering $A$.