Let G be a bridgeless cubic graph. The Berge–Fulkerson Conjecture (1970s) states that G admits a list of six perfect matchings such that each edge of G belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan–Raspaud Conjecture (1994), which states that G admits three perfect matchings such that every edge of G belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that G admits two perfect matchings whose deletion yields a bipartite subgraph of G. It can be shown that given an arbitrary perfect matching of G, it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan–Raspaud and the Berge–Fulkerson conjectures, respectively. In this paper, we show that given any 1+-factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G, there always exists a perfect matching M of G containing e such that G∖(F∪M) is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in G, there exists a perfect matching of G containing at least one edge of each circuit in this collection.

Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching / Kardoš, František; Máčajová, Edita; Zerafa, Jean Paul. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 160:(2023), pp. 1-14. [10.1016/j.jctb.2022.12.003]

Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching

Zerafa, Jean Paul
2023

Abstract

Let G be a bridgeless cubic graph. The Berge–Fulkerson Conjecture (1970s) states that G admits a list of six perfect matchings such that each edge of G belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan–Raspaud Conjecture (1994), which states that G admits three perfect matchings such that every edge of G belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that G admits two perfect matchings whose deletion yields a bipartite subgraph of G. It can be shown that given an arbitrary perfect matching of G, it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan–Raspaud and the Berge–Fulkerson conjectures, respectively. In this paper, we show that given any 1+-factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G, there always exists a perfect matching M of G containing e such that G∖(F∪M) is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in G, there exists a perfect matching of G containing at least one edge of each circuit in this collection.
2023
160
1
14
Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching / Kardoš, František; Máčajová, Edita; Zerafa, Jean Paul. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 160:(2023), pp. 1-14. [10.1016/j.jctb.2022.12.003]
Kardoš, František; Máčajová, Edita; Zerafa, Jean Paul
File in questo prodotto:
File Dimensione Formato  
2204.10021v2.pdf

Open access

Tipologia: AO - Versione originale dell'autore proposta per la pubblicazione
Dimensione 162.11 kB
Formato Adobe PDF
162.11 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/1373429
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 3
social impact