The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this article, we prove that deciding whether this number is at most four for a given cubic bridgeless graph is NP-complete. We also construct an infinite family F of snarks (cyclically 4-edge-connected cubic graphs of girth at least 5 and chromatic index 4) whose edge-set cannot be covered by four perfect matchings. Only two such graphs were known. It turns out that the family F also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with m edges has length at least 4m/3, and we show that this inequality is strict for graphs of F. We also construct the first known snark with no cycle cover of length less than 4m/3 + 2.

On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings / Esperet, L.; Mazzuoccolo, Giuseppe. - In: JOURNAL OF GRAPH THEORY. - ISSN 1097-0118. - 77:2(2014), pp. 144-157. [10.1002/jgt.21778]

On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings

Mazzuoccolo, Giuseppe
2014-01-01

Abstract

The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this article, we prove that deciding whether this number is at most four for a given cubic bridgeless graph is NP-complete. We also construct an infinite family F of snarks (cyclically 4-edge-connected cubic graphs of girth at least 5 and chromatic index 4) whose edge-set cannot be covered by four perfect matchings. Only two such graphs were known. It turns out that the family F also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with m edges has length at least 4m/3, and we show that this inequality is strict for graphs of F. We also construct the first known snark with no cycle cover of length less than 4m/3 + 2.
2014
77
2
144
157
On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings / Esperet, L.; Mazzuoccolo, Giuseppe. - In: JOURNAL OF GRAPH THEORY. - ISSN 1097-0118. - 77:2(2014), pp. 144-157. [10.1002/jgt.21778]
Esperet, L.; Mazzuoccolo, Giuseppe
File in questo prodotto:
File Dimensione Formato  
esperet_mazzuoccolo_revised.pdf

Accesso riservato

Dimensione 186.02 kB
Formato Adobe PDF
186.02 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/1310838
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 15
social impact