124 problems

Partition-graph de-anonymization conjecture. If a single user is de-anonymized by an optimizing attacker from $G$, the number of remaining perfect matchings is at most the number r…

For a perfect matching $M$ on $[2m]$, let ${\rm cr}(M)$ and ${\rm ne}(M)$ denote its numbers of crossings and nestings, respectively, and let ${\mathcal{M}}_{2m}$ be the set of per…

Let $G$ be a bridgeless cubic graph. Berge–Fulkerson conjecture. The graph $G$ has six perfect matchings such that each edge of $G$ is covered by exactly two of them. This longstan…

Let $G$ be a bridgeless cubic graph. Fan–Raspaud conjecture. The graph $G$ contains three perfect matchings $M_1,M_2,M_3$ such that no edge is covered by all three of them. The Ber…

Let $n\geq 2$ be an even integer. A perfect $1$-factorisation of a graph is a partition of its edge set into perfect matchings such that the union of any two distinct perfect match…

Let $G$ be a bridgeless cubic graph. Mazzuoccolo's conjecture. There exist two perfect matchings $M_1,M_2$ such that the graph obtained by deleting their union,…

Let $G$ be a bridgeless cubic graph. A collection of perfect matchings is an edge-covering collection when every edge of $G$ belongs to at least one matching in the collection. Ber…

For $0\leq t\leq r$, let $m(t,r)$ be the maximum integer $s$ such that every $t$-edge-connected $r$-graph has $s$ pairwise disjoint perfect matchings. The upper-bound conjecture. F…

Let $K_{n,n}$ be the complete bipartite graph with $n$ vertices in each part, and suppose its edges are partitioned into sets $E_1,\ldots,E_m$, where $m\leqslant n$. A perfect matc…

Let $G$ be a $d$-regular balanced bipartite graph on $2n$ vertices, and let $f4d8^{\mathbf{connect}}_{k,\mathrm{reg}}(n)$ denote the minimum-degree threshold for the $k$-switch gra…

Let $G$ be a bridgeless cubic graph. A perfect matching is a set of edges meeting every vertex exactly once, and an edge-cut is the set of edges joining a vertex subset to its comp…

Let $v=2n+1$ be an odd integer, let $K_v$ be the complete graph on $\{0,1,\ldots,v-1\}$, and let $L$ be a list of $n$ positive integers not exceeding $n$. A near $1$-factor $F$ is…

Let $G$ be a bridgeless cubic graph. A Fulkerson cover is a list of six perfect matchings of $G$ in which every edge is contained in exactly two matchings. Fulkerson's conjecture.…

Let $k$ and $\ell$ be integers with $1\leq\ell<k$, and let $H$ be a $k$-graph on $n$ vertices. Write $\delta_\ell(H)$ for the minimum $\ell$-degree and let $c^*_{k,\ell}$ be the fr…

Let $K_{2n}$ be the complete graph on $2n$ vertices, and let $\mathcal{F}$ be a family of perfect matchings of $K_{2n}$. The family is $t$-intersecting if any two of its members sh…

Let $G$ be a bridgeless cubic graph, and let a bipartite core mean a core whose underlying graph is bipartite. Bipartite core conjecture. Every bridgeless cubic graph has a biparti…

Let $G$ be a $2$-edge-connected cubic graph, and let $\omega(G)$ denote its oddness, the minimum number of odd circuits in a $2$-factor of $G$. Lukoťka–Máčajová–Mazák–Škoviera conj…

Let $A$ be a nonsingular alternating matrix, and let $D$ be the matrix-algebra deformation of $\mathbb{C}[\operatorname{coker} A]$ defined by the twisted relations in the paper. Le…

Balister–Győri–Schelp conjecture. If

A double wheel is the planar triangulation obtained by joining two vertices to every vertex of a cycle. A planar triangulation is 4-connected if it has no separating set of at most…

Let $k \ge 3$ and $n \ge 2k$ be integers, and let $G$ be a matchable $k$-connected graph with $n$ vertices. Zaks's conjecture. Every such graph satisfies … moreover, infinitely man…

Four-perfect-matchings conjecture. The perfect matching index of $G$ is at most $4$, unless $G$ is the Petersen graph.

Strong-snark conjecture. If the perfect matching index of $G$ is greater than $4$ and $G$ is not the Petersen graph, then $G$ is a strong snark.

Let $\delta^{\mathbf{no\ iso}}_k(n)$ denote the minimum-degree threshold such that the $k$-switch graph of an $n$-vertex graph, when nonempty, is guaranteed to have positive minimu…

Local spectral matching conjecture. If, for every $v\in V(H)$,