183 problems

Berge's conjecture. Five perfect matchings suffice to cover all the edges of $G$.

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…

A cubic bridgeless graph is a cubic graph in which no edge disconnects the graph. Lovász–Plummer conjecture. Every cubic bridgeless graph has an exponential number of perfect match…

Let $n$ be an even integer with $n\ge 4$. A $1$-factorisation of $K_n$ is a partition of its edge set into perfect matchings; two perfect matchings are called perfect when their un…

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…

Second-largest eigenvalue conjecture. If $\mu$ has at least two parts of size $1$, or if $\mu=[n-1,1]$ with $n\neq 4$, then the second largest eigenvalue of $A_\mu$ occurs on the i…

Let $G$ be a bridgeless cubic graph. A collection of six perfect matchings of $G$ may contain repetitions, and each edge of $G$ is counted according to its membership in the collec…

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 an $r$-graph be an $r$-regular graph $G$ such that every odd set $X\subseteq V(G)$ is connected by at least $r$ edges to its complement $V(G)\setminus X$. A graph is $r$-edge-c…

Pardey–Rautenbach conjecture. There is a perfect matching $M$ of $K_{2kn}$ such that

Perfect-matching threshold conjecture. The sharp $d$-threshold for $H_ncup G(n,p)$ to contain a perfect matching coincides with the threshold for $G(n,p)[B]$ to contain a matching…

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…

A Hexagonal Dungeon is the hexagonal counterpart of an Aztec Dungeon introduced by Matt Blum. Blum's conjecture. The number of tilings of a Hexagonal Dungeon is always given by a p…

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…

A $k$-graph is a hypergraph whose edges have size $k$. It is linear if every pair of distinct edges shares at most one vertex, and a loose hypertree is a connected linear $k$-graph…

Let $r=r(n)$ be an integer-valued function such that $r\mid 2n$, and let $G=K_{r\times 2n/r}$ be the balanced complete $r$-partite graph on $2n$ vertices. If $M$ is a perfect match…

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…

Keevash–Knox–Mycroft conjecture. For $1\leq\ell<k$, $\textbf{PM}(k,\ell,\delta)$ is in P for every

Let $FQ_n$ be the $n$-dimensional folded cube, let $E^m$ be a subset of $2^n-1$ edges of $FQ_n$, and let $FQ_n-E^m$ denote the graph obtained by deleting those edges. A perfect mat…

Bartha's conjecture. The unique perfect matching of $G$ can always be found in $O(m)$ time.

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…

Parity conjecture. The number of perfect matchings of the $n$-cube has the same parity as $n$ itself.

Let $G$ range over the family of subgraphs of the square lattice considered by Matt Blum, and let $u(G)$ denote the number of perfect matchings of $G$. Blum's conjecture. For…

Let an Aztec diamond of order $n$ be the union of all unit squares whose corners are lattice points satisfying $|x|+|y|\leq n+1$, and let a domino tiling be a covering of the regio…

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…