The Berge-Fulkerson conjecture, originally formulated in the language of mathematical programming, asserts that the edges of every bridgeless cubic (3-valent) graph can be covered with six perfect matchings in such a way that every edge is in exactly two of them. As with several other classical conjectures in graph theory, every counterexample to the Berge-Fulkerson conjecture must be a non-3-edge-colorable cubic graph. In contrast to Tutte's 5-flow conjecture and the cycle double conjecture, no nontrivial reduction is known for the Berge-Fulkerson conjecture. In the present paper, we prove that a possible minimum counterexample to the conjecture must be cyclically 5-edge-connected.
REDUCTION OF THE BERGE-FULKERSON CONJECTURE TO CYCLICALLY 5-EDGE-CONNECTED SNARKS / Macajova, E; Mazzuoccolo, G. - In: PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY. - ISSN 0002-9939. - 148:11(2020), pp. 4643-4652. [10.1090/proc/15057]
REDUCTION OF THE BERGE-FULKERSON CONJECTURE TO CYCLICALLY 5-EDGE-CONNECTED SNARKS
Mazzuoccolo, G
2020
Abstract
The Berge-Fulkerson conjecture, originally formulated in the language of mathematical programming, asserts that the edges of every bridgeless cubic (3-valent) graph can be covered with six perfect matchings in such a way that every edge is in exactly two of them. As with several other classical conjectures in graph theory, every counterexample to the Berge-Fulkerson conjecture must be a non-3-edge-colorable cubic graph. In contrast to Tutte's 5-flow conjecture and the cycle double conjecture, no nontrivial reduction is known for the Berge-Fulkerson conjecture. In the present paper, we prove that a possible minimum counterexample to the conjecture must be cyclically 5-edge-connected.File | Dimensione | Formato | |
---|---|---|---|
macajova_mazzuoccolo_r.pdf
Accesso riservato
Dimensione
326.3 kB
Formato
Adobe PDF
|
326.3 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris