102 problems

Does there exist a positive integer $N$ such that, for every integer $n\ge N$, the maximum number of edges in a simple solid matching-covered graph on $2n$ vertices is $n^2$? Here…

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 $G$ be a minimal $k$-extendable claw-free graph, meaning that $G$ is $k$-extendable and deleting any edge produces a graph that is not $k$-extendable. Let $\delta(G)$ denote it…

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…

Aouchiche–Hansen–Zheng conjecture. One has

Favaron–Shi's conjecture. If $G$ is a minimal $k$-factor-critical graph, then

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…

Balister–Győri–Schelp conjecture. There exists a partition of $\mathbb F_2^k$ into 2-sets $\{w_i,z_i\}$, for $i\in\{1,\dots,2^{k-1}\}$, such that

3-extendability conjecture. Every $8$-regular optimal $1$-embedded graph $G$ on the Klein bottle is $3$-extendable.

Let $\mathcal{L}\in\mathcal{D}^k$ be a family of $k$ matroids on $V$, and let $w\in\mathbb{R}_{\ge0}^V$. Weighted fractional matching-cover conjecture. One has … This is presented…

Randić-index matching conjecture. If

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