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

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-01
Main Authors: Mazzuoccolo, Giuseppe, Zerafa, Jean Paul
Format: Article
Language:English
Subjects:
Equivalence
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1811.08363