
cubic
Exponentially many perfect matchings in cubic graphs ★★★
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
?





The intersection of two perfect matchings ★★
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
The Berge-Fulkerson conjecture ★★★★
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
