Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Jean Paul Zerafa (17.10.2019)

vo štvrtok 17.10.2019 o 9:50 hod. v miestnosti M/213

14. 10. 2019 13.00 hod.
Od: Martin Škoviera

Prednášajúci: Jean Paul Zerafa (Universita` degli Studi di Modena e Reggio Emilia)

Názov: An equivalent formulation of the Fan-Raspaud Conjecture and related problems

Termín: 17.10.2019, 9:50 hod., M/213

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 talk we solve a problem recently proposed by Mkrtchyan and Vardanyan by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture 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. We here show that this conjecture can be equivalently stated using $H$-colourings, we prove it for graphs having oddness at most four and extend it to bridgeless cubic multigraphs and certain cubic graphs having bridges. Other related conjectures and their connection to the above will also be discussed.

This is a joint work with Giuseppe Mazzuoccolo.