![](/files/happy5.png)
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.
![$ c $](/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ e^{cn} $](/files/tex/22656fabb8498ada6bf54e6068c4978436afcc8f.png)
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
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ C $](/files/tex/05d3558ef52267cc1af40e658352d98883668ee3.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ C' \neq C $](/files/tex/c3199a0094ee88c4571a3a65defc88a4343532ca.png)
![$ V(C) \subseteq V(C') $](/files/tex/e5b68d14640cffba06d035388ad1465bb885f72e.png)
The intersection of two perfect matchings ★★
Conjecture Every bridgeless cubic graph has two perfect matchings
,
so that
does not contain an odd edge-cut.
![$ M_1 $](/files/tex/6053a26729abbb4d69de99ccd5976244ef2773c9.png)
![$ M_2 $](/files/tex/b0ecd935059283a5c903e8bbf8faf28490053d61.png)
![$ M_1 \cap M_2 $](/files/tex/15325788d4a123d31609b6e498c31ecaca4b6f19.png)
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
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ G \to C_5 $](/files/tex/090efbbd450a0134afde46b53f2dbe35011946d1.png)
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
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ M_1,\ldots,M_6 $](/files/tex/8ab42e6cd40fd3556882bbb8216d0b8e14f3bf3e.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ M_1,\ldots,M_6 $](/files/tex/8ab42e6cd40fd3556882bbb8216d0b8e14f3bf3e.png)
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 Syndicate content](/misc/feed.png)