perfect matching

Exponentially many perfect matchings in cubic graphs ★★★

Author(s): Lovasz; Plummer

\begin{conjecture} There exists a fixed constant $c$ so that every $n$-vertex cubic graph without a cut-edge has at least $e^{cn}$ perfect matchings. \end{conjecture}

Keywords: cubic; perfect matching

The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

\begin{conjecture} Every bridgeless cubic graph has two perfect matchings $M_1$, $M_2$ so that $M_1 \cap M_2$ does not contain an odd edge-cut. \end{conjecture}

Keywords: cubic; nowhere-zero flow; perfect matching

The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

\begin{conjecture} If $G$ is a \Def[bridgeless]{bridge (graph theory)} \Def[cubic]{cubic graph} graph, then there exist 6 \Def[perfect matchings]{matching} $M_1,\ldots,M_6$ of $G$ with the property that every edge of $G$ is contained in exactly two of $M_1,\ldots,M_6$.


Keywords: cubic; perfect matching

Syndicate content