In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridges.

An equivalent formulation of the Fan-Raspaud Conjecture and related problems / Mazzuoccolo, G; Zerafa, Jp. - In: ARS MATHEMATICA CONTEMPORANEA. - ISSN 1855-3966. - 18:1(2020), pp. 87-103. [10.26493/1855-3974.1860.a3d]

An equivalent formulation of the Fan-Raspaud Conjecture and related problems

Mazzuoccolo, G;
2020

Abstract

In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridges.
2020
18
1
87
103
An equivalent formulation of the Fan-Raspaud Conjecture and related problems / Mazzuoccolo, G; Zerafa, Jp. - In: ARS MATHEMATICA CONTEMPORANEA. - ISSN 1855-3966. - 18:1(2020), pp. 87-103. [10.26493/1855-3974.1860.a3d]
Mazzuoccolo, G; Zerafa, Jp
File in questo prodotto:
File Dimensione Formato  
Paper.pdf

Open access

Tipologia: Versione pubblicata dall'editore
Dimensione 326.68 kB
Formato Adobe PDF
326.68 kB Adobe PDF Visualizza/Apri
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/1310839
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact