Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1-factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge-set of G can be covered with at most five 1-factors. We prove that the two conjectures are equivalent.
The equivalence of two conjectures of Berge and Fulkerson
Mazzuoccolo, Giuseppe
2011-01-01
Abstract
Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1-factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge-set of G can be covered with at most five 1-factors. We prove that the two conjectures are equivalent.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
mazzuoccolo_JGT-09-276.pdf
non disponibili
Descrizione: Articolo Principale
Tipologia:
Documento in Pre-print
Licenza:
Accesso ristretto
Dimensione
90.52 kB
Formato
Adobe PDF
|
90.52 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
