14:00
15:00

[gt.go] - "Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching" by František Kardoš

/Exposé en anglais/Talk in english/

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

This is a joint work with Edita Máčajová and Jean Paul Zerafa.

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

https://webconf.u-bordeaux.fr/b/mar-ef4-zed ou au LaBRI/178