A conjecture of Berge and Fulkerson (1971) states that every cubic bridgeless graph contains 6 perfect matchings covering each edge precisely twice, which easily implies that every cubic bridgeless graph has three perfect matchings with empty intersection (this weaker statement was conjectured by Fan and Raspaud in 1994). Let mt be the supremum of all reals α≤1 such that for every cubic bridgeless graph G, there exist t perfect matchings of G covering a fraction of at least α of the edges of G. It is known that the Berge-Fulkerson conjecture is equivalent to the statement that =1, and implies that =1415 and =45. In the first part of this paper, we show that m4=1415 implies =45, and =45 implies the Fan-Raspaud conjecture, strengthening a recent result of Tang, Zhang, and Zhu. In the second part of the paper, we prove that for any 2≤t≤4 and for any real τ lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) τ of the edges of a given cubic bridgeless graph can be covered by t perfect matching is an NP-complete problem.

On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph / Esperet, Louis; Mazzuoccolo, Giuseppe. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 338:8(2015), pp. 1509-1514. [10.1016/j.disc.2015.03.017]

On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph

Mazzuoccolo, Giuseppe
2015

Abstract

A conjecture of Berge and Fulkerson (1971) states that every cubic bridgeless graph contains 6 perfect matchings covering each edge precisely twice, which easily implies that every cubic bridgeless graph has three perfect matchings with empty intersection (this weaker statement was conjectured by Fan and Raspaud in 1994). Let mt be the supremum of all reals α≤1 such that for every cubic bridgeless graph G, there exist t perfect matchings of G covering a fraction of at least α of the edges of G. It is known that the Berge-Fulkerson conjecture is equivalent to the statement that =1, and implies that =1415 and =45. In the first part of this paper, we show that m4=1415 implies =45, and =45 implies the Fan-Raspaud conjecture, strengthening a recent result of Tang, Zhang, and Zhu. In the second part of the paper, we prove that for any 2≤t≤4 and for any real τ lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) τ of the edges of a given cubic bridgeless graph can be covered by t perfect matching is an NP-complete problem.
2015
338
8
1509
1514
On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph / Esperet, Louis; Mazzuoccolo, Giuseppe. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 338:8(2015), pp. 1509-1514. [10.1016/j.disc.2015.03.017]
Esperet, Louis; Mazzuoccolo, Giuseppe
File in questo prodotto:
File Dimensione Formato  
pm_esp_maz-revised.pdf

Accesso riservato

Dimensione 264.99 kB
Formato Adobe PDF
264.99 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
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

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