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

Bigger cycles in cubic graphs ★★


\begin{problem} Let $G$ be a cyclically 4-edge-connected cubic graph and let $C$ be a cycle of $G$. Must there exist a cycle $C' \neq C$ so that $V(C) \subseteq V(C')$? \end{problem}

Keywords: cubic; cycle

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

Barnette's Conjecture ★★★

Author(s): Barnette

\begin{conjecture} Every 3-connected cubic planar bipartite graph is Hamiltonian. \end{conjecture}

Keywords: bipartite; cubic; hamiltonian

Pentagon problem ★★★

Author(s): Nesetril

\begin{question} Let $G$ be a 3-regular graph that contains no cycle of length shorter than $g$. Is it true that for large enough~$g$ there is a \Def[homomorphism]{graph_homomorphism} $G \to C_5$? \end{question}

Keywords: cubic; homomorphism

Petersen coloring conjecture ★★★

Author(s): Jaeger

\begin{conjecture} Let $G$ be a \Def[cubic]{cubic graph} graph with no \Def[bridge]{bridge (graph theory)}. Then there is a coloring of the edges of $G$ using the edges of the \Def[Petersen]{petersen graph} graph so that any three mutually adjacent edges of $G$ map to three mutually adjancent edges in the Petersen graph. \end{conjecture}

Keywords: cubic; edge-coloring; Petersen graph

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

5-flow conjecture ★★★★

Author(s): Tutte

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph has a \Def[nowhere-zero]{nowhere-zero flows} 5-flow. \end{conjecture}

Keywords: cubic; nowhere-zero flow

Syndicate content