101 problems

Multiplicity Ryser-Brualdi-Stein conjecture. There exists a matching $M$ in $G$ such that

Let $G$ be a graph on $2n$ vertices whose edge set is decomposed into perfect matchings $M_1$, $M_2$, and $M_3$, and let $a_1$, $a_2$, and $a_3$ be non-negative integers satisfying…

Xu et al.'s conjecture. The maximum forcing number of $G$ can be computed in polynomial time.

Let $G$ be a finite simple graph. It is factor-critical if, for every vertex $v\in V(G)$, the graph $G-v$ has a perfect matching. The graph $G$ is $K_{1,5}$-free if it has no induc…

The Asymptotic Lower $r$-Permanent Conjecture. Under these hypotheses,

The Asymptotic Upper Matching Conjecture. Under these hypotheses,

The Upper Matching Conjecture. One has

The Asymptotic Lower Matching Conjecture. Under these hypotheses,

Let $\{G_k=(V_k,E_k)\}_{k\in\mathbb{N}}$ be a sequence of $r$-regular bipartite graphs with $\#V_k\to\infty$. Let $h_{\{G_k\}}(p)$ denote the associated monomer–dimer entropy, and…

Let $P$ be a poset containing no infinite antichain. A chain is a pairwise comparable subset of $P$, and an antichain is a pairwise incomparable subset. Fish-scale conjecture. Ther…

In the two-sided secretary game, suppose there are $U$ men and $U$ women, each player meets $N$ partners over $N$ rounds, and preferences satisfy universal rank symmetry: if a man…

Finite-termination conjecture. If $\pi^*$ is unique, then the min-sum auction I algorithm terminates after finitely many iterations when this condition is removed from step (4).

Let $k\geq2$, $s\geq1$, $1\leq r\leq k-1$, and let $p\geq1$ be real. Suppose that … If $\mathcal F\subseteq\binom{[n]}k$ satisfies $\nu(\mathcal F)\leq s$, let $\mathcal B_S$ denot…

Two-barrier Ore-degree conjecture. If

Aouchiche–Hansen–Zheng conjecture. One has

Let $G$ be a finite simple graph with $n$ non-isolated vertices. Let $L(G)$ be its Laplacian matrix, let $\lambda_1(G)\ge\cdots\ge\lambda_n(G)$ be the Laplacian eigenvalues, and wr…

Let $M_s^r$ be a matching of size $s$ in an $r$-uniform hypergraph, and let $\operatorname{ex}_r(n,M_s^r)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergrap…

Let $G$ be a connected simple graph, and let $\mu^{*}(G)$ denote its saturation number, the minimum cardinality of a maximal matching. Let … be its harmonic index. A graph is subqu…

Let $G$ be a $k$-connected graph on $n$ vertices with minimum degree $\delta(G)\ge k+2$. A matching is $k$-removable when deleting its edges leaves a $k$-connected graph. The maxim…

For $k\ge 1$, a vertex set $S$ in a $k$-connected graph $G$ is $k$-removable when $G-S$ remains $k$-connected; a matching is $k$-removable when its edge deletion leaves a $k$-conne…

For integers $n\ge s\ge2$, define … For integers $m\ge1$ and $1\le\ell\le\lceil s/2\rceil$, set $n=(m+1)s-\ell$ and, for any $L\in\binom{[n]}{\ell-1}$, define … and write…

Let $K_{\ell+1}^{(r)+}$ be the $r$-uniform expansion of the complete graph on $\ell+1$ vertices, let $M_{s+1}^{(r)+}$ be an $r$-uniform matching with $s+1$ edges, and let…

Let $K^{(r)+}_{\ell+1}$ be the $r$-uniform expansion of the complete graph on $\ell+1$ vertices, let $M^{(r)+}_{s+1}$ be an $r$-uniform matching with $s+1$ edges, and let…

Let $G$ be an almost bipartite non-König–Egerváry graph, and let $C$ be its unique odd cycle. A maximum matching of $G$ is a matching with the largest possible number of edges. Lev…

Akbari–Alazemi–Anđelić's conjecture. For any connected graph $G \not\cong C_3, C_5, C_7$ with $\Delta(G) \in \{ 2, 3, 4, 5 \}$, we have