The Fulkerson conjecture states that every bridgeless cubic graph has a collection of six perfect
matchings such that each edge belongs to exactly two
of them. Mazzuoccolo (2011) showed that this is equivalent to Berge's
conjecture that every bridgeless cubic
graph should have perfect matching
cover index at most 5.
The Fulkerson conjecture is a dual form of the cycle double cover conjecture . Cubic graphs with perfect matching cover index at least
5 are therefore important test objects for this and related conjectures (Máčajová
and Škoviera 2021).
See also Berge Perfect Matching Conjecture ,
Bridgeless Graph ,
Cycle
Double Cover Conjecture ,
Perfect Matching ,
Perfect Matching Cover Index ,
Snark
Explore with Wolfram|Alpha
References Máčajová, E. and Škoviera, M. "Cubic Graphs That Cannot Be Covered with Four Perfect Matchings." J.
Combin. Th. Ser. B 150 , 144-176, 2021. https://doi.org/10.1016/j.jctb.2021.04.004 . Mazzuoccolo,
G. "The Equivalence of Two Conjectures of Berge and Fulkerson." J. Graph
Th. 68 , 125-128, 2011.
Cite this as:
Weisstein, Eric W. "Fulkerson Conjecture."
From MathWorld https://mathworld.wolfram.com/FulkersonConjecture.html
Subject classifications
