Exponentially many perfect matchings in cubic graphs ★★★

Author(s): Lovasz; Plummer

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.

Keywords: cubic; perfect matching

Bigger cycles in cubic graphs ★★


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') $?

Keywords: cubic; cycle

The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

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.

Keywords: cubic; nowhere-zero flow; perfect matching

Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

Pentagon problem ★★★

Author(s): Nesetril

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 homomorphism $ G \to C_5 $?

Keywords: cubic; homomorphism

Petersen coloring conjecture ★★★

Author(s): Jaeger

Conjecture   Let $ G $ be a cubic graph with no bridge. Then there is a coloring of the edges of $ G $ using the edges of the Petersen graph so that any three mutually adjacent edges of $ G $ map to three mutually adjancent edges in the Petersen graph.

Keywords: cubic; edge-coloring; Petersen graph

The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

Conjecture   If $ G $ is a bridgeless cubic graph, then there exist 6 perfect matchings $ 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

Conjecture   Every bridgeless graph has a nowhere-zero 5-flow.

Keywords: cubic; nowhere-zero flow

Syndicate content