Percorso pagina:

# Giuseppe Mazzuoccolo

INdAM-COFUND Outgoing fellow between 2012-06-18 and 2014-06-17

### Project information

#### Title

MCGM: Minimum Coverings of Graphs with Matchings

#### Outgoing host organisation Return host organisation

Laboratoire G-SCOP Universit degli Studi di Modena e Reggio Emilia

Avenue FÃ©lix Viallet, 46 Dipartimento di Matematica Pura ed Applicata

38031 Grenoble, France Via Campi 213/b, 41125 Modena, Italy

http://www.g-scop.inpg.fr/ http://www.unimore.it/

Abstract

The topic of this project is within Graph Theory, in particular it lies in the area of Matching Theory. In the first half of the previous century Hall, Petersen and Tutte laid the foundations of Matching Theory with the theorems which today bear their

names. Their celebrated results give necessary and sufficient conditions for certain classes of graphs to admit a perfect matching.

The main difference between these classical results and the goals of this project lies in the primary object of the

investigation: while the former focussed on the single perfect matching, this project investigates properties of the entire set of perfect matchings of a graph.

The trigger for this kind of investigations can be attributed to the Berge-Fulkerson conjecture, a very challenging open

problem in the field. Around 1970, Berge and Fulkerson independently conjectured that each bridgeless cubic graph G can be covered with six perfect matchings in such a way that each edge of G lies in exactly two of them.

The Berge-Fulkerson conjecture would have two straightforward implications. The first one is that the edge-set of each bridgeless cubic graph could be covered with at most five perfect matchings. The second one would state the existence of three perfect matchings of G with empty intersection. This two natural consequences lead to two well-known conjectures: the former is attributed to Berge himself and the latter to Fan and Raspaud.

We recently proved the equivalence between the Berge conjecture and the Berge-Fulkerson conjecture. This result is the

starting point for a general investigation on properties involving the union and the intersection of perfect matchings of a graph.

### Fellow information

#### Research interests

Matching theory, Berge-Fulkerson conjecture, symmetric decompositions and colorings, fullerene graphs.

#### Previous positions, awards

*2007-2011*: Post doc, Dipartimento di Matematica

Pura ed Applicata, UniversitÃ di Modena e Reggio Emilia

#### Publications, preprints, other works

- S. Bonvicini, G. Mazzuoccolo,
*A new description of Perfectly one-factorable cubic graphs*, Atti Semin. Mat. Fis. Univ. Modena Reggio Emilia 54 (2006), 167-173 - A. Bonisoli, M. Buratti, G. Mazzuoccolo,
*Doubly transitive 2-factorizations*, Journal of Combinatorial Designs 15 (2007), 120-132 - G. Mazzuoccolo, G. Rinaldi,
*k-pyramidal one-factorizations*, Graphs and Combinatorics 23 (2007), 315-326 - G. Mazzuoccolo,
*Primitive 2-factorizations of the complete graph*, Discrete Mathematics 308 (2008), 175-179 - G. Mazzuoccolo,
*On 2-factorizations whose automorphism group acts doubly transitively on the factors*, Discrete Mathematics 308 (2008), 931-939 - G. Mazzuoccolo,
*Perfect one-factorizations in line-graphs and planar graphs*, Australasian Journal of Combinatorics 41 (2008), 227-233 - S. Bonvicini, G. Mazzuoccolo, G. Rinaldi,
*On 2-factorizations of the complete graph: from the k-pyramidal to the universal property*, Journal of Combinatorial Designs 17 (2009), 211-228 - G. Mazzuoccolo, B. Ruini,
*On automorphic chromatic index of Generalized Petersen graphs*, AKCE Journal of Graphs and Combinatorics 6 (2009), 429-437 - S. Kurz, G. Mazzuoccolo,
*On matchsticks graphs with given girth*, Geombinatorics 19 (2009), 156-175 - C. Fiori, G. Mazzuoccolo, B. Ruini,
*On the automorphic chromatic index of a graph*, Graphs and Combinatorics 26 (2010), 685-694 - G. Mazzuoccolo, G. Rinaldi,
*Sharply transitive one-factorizations of complete multipartite graphs*, Electronic Journal of Combinatorics 17 (2010), R77 - S. Bonvicini, G. Mazzuoccolo,
*Abelian one-factorizations of infinite complete graphs*, European Journal of Combinatorics 31 (2010), 1847-1852 - G. Mazzuoccolo,
*NP-completeness of automorphic colorings*, Discussiones Mathematicae Graph Theory 30 (2010), 705-710 - C. Fiori, G. Mazzuoccolo, B. Ruini,
*Automorphic chromatic index of infinite classes of snarks*, Results in Mathematics 58 (2010), 241-254 - G. Mazzuoccolo, M. Young,
*Graphs of arbitrary excessive class*, Discrete Mathematics 311 (2011), 32-37 - S. Bonvicini, G. Mazzuoccolo,
*Perfect one-factorizations in Generalized Petersen graphs*, Ars Combinatoria 99 (2011), 33-43 - M. Bogaerts, G. Mazzuoccolo,
*Cyclic and dihedral 1-factorizations of multipartite graphs*, Electronic Journal of Combinatorics 18 (2011), R179 - G. Mazzuoccolo,
*The equivalence of two conjectures of Berge and Fulkerson*, Journal of Graph Theory 68 (2011), 125-128 - G. Mazzuoccolo,
*An upper bound for the excessive index of an r-graph*, to appear on Journal of Graph Theory - G. Mazzuoccolo, B. Ruini,
*Automorphic chromatic index of graphs with abelian automorphism groups*, submitted - G. Mazzuoccolo,
*Covering a 3-graph with perfect matchings*, submitted - M. Bogaerts, G. Mazzuoccolo, G. Rinaldi,
*Totally symmetric KekulÃš structure in fullerene graphs with ten or more symmetries*, MATCH Commun. Math. Comput. Chem. 69 (2013) 677-705 - S. Bonvicini, G. Mazzuoccolo ,
*Covering cubic graphs with matchings of large size*, submitted

#### Conferences, schools, other events

*JCRAA 2012: Quelques aspects de l’entropie en combinatoire*

Lyon, France, 28-29 June 2012*International Conference Combinatorics 2012*

Perugia, Italy, 9-15 September 2012*Bordeaux Graph Workshop*

Bordeaux, France, 21-24 November 2012