# cubic

## Exponentially many perfect matchings in cubic graphs ★★★

Author(s): Lovasz; Plummer

Conjecture   There exists a fixed constant so that every -vertex cubic graph without a cut-edge has at least perfect matchings.

Keywords: cubic; perfect matching

## Bigger cycles in cubic graphs ★★

Author(s):

Problem   Let be a cyclically 4-edge-connected cubic graph and let be a cycle of . Must there exist a cycle so that ?

Keywords: cubic; cycle

## The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

Conjecture   Every bridgeless cubic graph has two perfect matchings , so that 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 be a 3-regular graph that contains no cycle of length shorter than . Is it true that for large enough~ there is a homomorphism ?

Keywords: cubic; homomorphism

## Petersen coloring conjecture ★★★

Author(s): Jaeger

Conjecture   Let be a cubic graph with no bridge. Then there is a coloring of the edges of using the edges of the Petersen graph so that any three mutually adjacent edges of 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 is a bridgeless cubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .

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 