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.
1-factors, Berge-Fulkerson conjecture, Cubic graph, perfect matchings
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/927860
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? 35
social impact