Menù superiore:

INdAM Cofund

INdAM Fellowship Programs in Mathematics and/or Applications cofunded by Marie Skłodowska-Curie Actions

Percorso pagina:

Giuseppe Mazzuoccolo

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

Project information


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                                  


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

  1. 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
  2. A. Bonisoli, M. Buratti, G. Mazzuoccolo, Doubly transitive 2-factorizations, Journal of Combinatorial Designs 15 (2007), 120-132
  3. G. Mazzuoccolo, G. Rinaldi, k-pyramidal one-factorizations, Graphs and Combinatorics 23 (2007), 315-326
  4. G. Mazzuoccolo, Primitive 2-factorizations of the complete graph, Discrete Mathematics 308 (2008), 175-179
  5. G. Mazzuoccolo, On 2-factorizations whose automorphism group acts doubly transitively on the factors, Discrete Mathematics 308 (2008), 931-939
  6. G. Mazzuoccolo, Perfect one-factorizations in line-graphs and planar graphs, Australasian Journal of Combinatorics 41 (2008), 227-233
  7. 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
  8. G. Mazzuoccolo, B. Ruini, On automorphic chromatic index of Generalized Petersen graphs, AKCE Journal of Graphs and Combinatorics 6 (2009), 429-437
  9. S. Kurz, G. Mazzuoccolo, On matchsticks graphs with given girth, Geombinatorics 19 (2009), 156-175
  10. C. Fiori, G. Mazzuoccolo, B. Ruini, On the automorphic chromatic index of a graph, Graphs and Combinatorics 26 (2010), 685-694
  11. G. Mazzuoccolo, G. Rinaldi, Sharply transitive one-factorizations of complete multipartite graphs, Electronic Journal of Combinatorics 17 (2010), R77
  12. S. Bonvicini, G. Mazzuoccolo, Abelian one-factorizations of infinite complete graphs, European Journal of Combinatorics 31 (2010), 1847-1852
  13. G. Mazzuoccolo, NP-completeness of automorphic colorings, Discussiones Mathematicae Graph Theory 30 (2010), 705-710
  14. C. Fiori, G. Mazzuoccolo, B. Ruini, Automorphic chromatic index of infinite classes of snarks, Results in Mathematics 58 (2010), 241-254
  15. G. Mazzuoccolo, M. Young, Graphs of arbitrary excessive class, Discrete Mathematics 311 (2011), 32-37
  16. S. Bonvicini, G. Mazzuoccolo, Perfect one-factorizations in Generalized Petersen graphs, Ars Combinatoria 99 (2011), 33-43
  17. M. Bogaerts, G. Mazzuoccolo, Cyclic and dihedral 1-factorizations of multipartite graphs, Electronic Journal of Combinatorics 18 (2011), R179
  18. G. Mazzuoccolo, The equivalence of two conjectures of Berge and Fulkerson, Journal of Graph Theory 68 (2011), 125-128
  19. G. Mazzuoccolo, An upper bound for the excessive index of an r-graph, to appear on Journal of Graph Theory
  20. G. Mazzuoccolo, B. Ruini, Automorphic chromatic index of graphs with abelian automorphism groups, submitted
  21. G. Mazzuoccolo, Covering a 3-graph with perfect matchings, submitted
  22. 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
  23. 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

Amministrazione Accessibile – Sviluppato da Spazio Sputnik – Basato su Bootstrap 3

Sito realizzato con "Amministrazione Accessibile", il tema Wordpress per la Pubblica Amministrazione e gli Enti non profit.