/Exposé /Talk/

Let G be a bridgeless cubic graph. Recently, in collaboration with Edita Máčajová and Jean Paul Zerafa, we have solved a conjecture (also known as the S4-Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchings of G such that the complement of their union is a bipartite subgraph of G. (There was a talk on this topic in June 2022.)

This is a step closer to comprehend better the Fan--Raspaud Conjecture and eventually the Berge--Fulkerson Conjecture. The S4-Conjecture, now a theorem, is also the weakest assertion in a series of three conjectures made by Mazzuoccolo in 2013, with the next stronger statement being: there exist two perfect matchings of G such that the complement of their union is an acyclic subgraph of G. Unfortunately, this conjecture is not true: Jin, Steffen, and Mazzuoccolo showed that there exists a counterexample admitting 2-cuts. Here we show that, despite of this, every cyclically 3-edge-connected cubic graph satisfies this second conjecture.

[František Kardoš] (Université de Bordeaux, LaBRI )
https://www.labri.fr/perso/fkardos/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .