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…

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…

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. 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 $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…

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…

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…

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

Let $M$ be a matrix with non-negative real entries, let $t$ be an odd positive integer, and let $(x_1,y_1),\ldots,(x_t,y_t)$ be distinct entries of $M$ satisfying $M_{x_i y_i}=0$ f…

Let a bipartite labeled multigraph be a tuple $(L,R,E,u,v)$, where $u:E\to L$ and $v:E\to R$. Let $A_{n,k}$ be the set of biregular bipartite labeled multigraphs with $L=[n]$,…

Let $M$ be a binary $n\times k$ matrix with non-negative integer entries, row sums $k$, and column sums $n$. Let $M\otimes M^T$ be the matrix associated with the corresponding tens…

Let $M$ be a binary $n\times k$ matrix. Define $M\otimes M^T$ to be the symmetric $nk\times nk$ matrix indexed by pairs in $[n]\times[k]$, with entries … A perfect matching is an i…

Let $G$ be a finite simple graph of order $2n$ with a perfect matching. Write $e(G)$ for the number of edges of $G$, and let $F(G)$ denote its maximum forcing number. Liu–Zhang's c…

Largest-diameter conjecture. The diameter of $X_{[2,1^{n-2}]}$ is the largest diameter among all graphs in the perfect matching association scheme.

Smallest spectral-gap conjecture. Among the adjacency matrices

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 $\mathcal{M}_n$ be the set of labelled perfect matchings, equipped with the preorder $\preceq$. Antisymmetry conjecture. The preorder $(\mathcal{M}_n,\preceq)$ is a poset; equi…

Let $\mathcal{M}_n$ be the set of the labelled perfect matchings under consideration, and let $\preceq$ be the preorder on this set. A switch is the local transformation defined ea…

Let $n\ge 3$ be an integer, and let $(d_1^1,\ldots,d_n^1)$ and $(d_1^2,\ldots,d_n^2)$ be graphic sequences with $d_n^1,d_n^2\ge 1$. Two graphic sequences pack when there are edge-d…