Nuova ricerca

Giuseppe MAZZUOCCOLO

Professore Associato
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica

Home | Curriculum(pdf) | Didattica |


Pubblicazioni

2023 - A Characterization of Graphs with Small Palette Index [Articolo su rivista]
Labbate, D.; Mattiolo, D.; Mazzuoccolo, G.; Romaniello, F.; Tabarelli, G.
abstract

Given an edge-coloring of a graph G, we associate to every vertex v of G the set of colors appearing on the edges incident with v. The palette index of G is defined as the minimum number of such distinct sets, taken over all possible edge-colorings of G. A graph with a small palette index admits an edge-coloring which can be locally considered to be almost symmetric, since few different sets of colors appear around its vertices. Graphs with palette index 1 are r-regular graphs admitting an r-edge-coloring, while regular graphs with palette index 2 do not exist. Here, we characterize all graphs with palette index either 2 or 3 in terms of the existence of suitable decompositions in regular subgraphs. As a corollary, we obtain a complete characterization of regular graphs with palette index 3.

2023 - On the existence of graphs which can colour every regular graph [Articolo su rivista]
Mazzuoccolo, G.; Tabarelli, G.; Zerafa, J. P.
abstract

Let H and G be graphs. An H-colouring of G is a proper edge-colouring f : E(G) -> E(H) such that for any vertex u E V(G) there exists a vertex v E V(H) with f (8Gu) = 8Hv, where 8Gu and 8Hv respectively denote the sets of edges in G and H incident to the vertices u and v. If G admits an H-colouring we say that H colours G. The question whether there exists a graph H that colours every bridgeless cubic graph is addressed directly by the Petersen Colouring Conjecture, which states that the Petersen graph colours every bridgeless cubic graph. In 2012, Mkrtchyan showed that if this conjecture is true, the Petersen graph is the unique connected bridgeless cubic graph H which can colour all bridgeless cubic graphs. In this paper we extend this and show that if we were to remove all degree conditions on H, every bridgeless cubic graph G can be coloured substantially only by a unique other graph: the subcubic multigraph S4 on four vertices. A few similar results are provided also under weaker assumptions on the graph G. In the second part of the paper, we also consider H-colourings of regular graphs having degree strictly greater than 3 and show that: (i) for any r > 3, there does not exist a connected graph H (possibly containing parallel edges) that colours every r-regular multigraph, and (ii) for every r > 1, there does not exist a connected graph H (possibly containing parallel edges) that colours every 2r-regular simple graph.(c) 2023 Elsevier B.V. All rights reserved.

2022 - Graphs with large palette index [Articolo su rivista]
Mattiolo, D.; Mazzuoccolo, G.; Tabarelli, G.
abstract

Given an edge-coloring of a graph, the palette of a vertex is defined as the set of colors of the edges which are incident with it. We define the palette index of a graph as the minimum number of distinct palettes, taken over all edge-colorings, occurring among the vertices of the graph. Several results about the palette index of some specific classes of graphs are known. In this paper we propose a different approach that leads to new and more general results on the palette index. Our main theorem gives a sufficient condition for a graph to have palette index larger than its minimum degree. In the second part of the paper, by using such a result, we answer to two open problems on this topic. First, for every r odd, we construct a family of r-regular graphs with palette index reaching the maximum admissible value. After that, we construct the first known family of simple graphs whose palette index grows quadratically with respect to their maximum degree.

2021 - A unified approach to construct snarks with circular flow number 5 [Articolo su rivista]
Goedgebeur, Jan; Mattiolo, Davide; Mazzuoccolo, Giuseppe
abstract

The well-known 5-flow Conjecture of Tutte, stated originally for integer flows, claims that every bridgeless graph has circular flow number at most 5. It is a classical result that the study of the 5-flow Conjecture can be reduced to cubic graphs, in particular to snarks. However, very few procedures to construct snarks with circular flow number 5 are known. In the first part of this paper, we summarise some of these methods and we propose new ones based on variations of the known constructions. Afterwards, we prove that all such methods are nothing but particular instances of a more general construction that we introduce into detail. In the second part, we consider many instances of this general method and we determine when our method permits to obtain a snark with circular flow number 5. Finally, by a computer search, we determine all snarks having circular flow number 5 up to 36 vertices. It turns out that all such snarks of order at most 34 can be obtained by using our method, and that the same holds for 96 of the 98 snarks of order 36 with circular flow number 5.

2021 - Extending perfect matchings to Hamiltonian cycles in line graphs [Articolo su rivista]
Abreu, M; Gauci, Jb; Labbate, D; Mazzuoccolo, G; Zerafa, Jp
abstract

A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph G in order to guarantee that its line graph L(G) has the PMH-property. In particular, we prove that this happens when G is (i) a Hamiltonian graph with maximum degree at most 3, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper.

2021 - On sublinear approximations for the Petersen coloring conjecture [Articolo su rivista]
Mattiolo, D.; Mazzuoccolo, G.; Mkrtchyan, V.
abstract

2021 - On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching [Articolo su rivista]
Mazzuoccolo, Giuseppe; Mella, Lorenzo
abstract

Let G be a finite graph (without loops and multiple edges) and let w : E(G) -> [0,+infinity) be a weight function on the edge set of G. We consider the ratio between the maximum weight of a perfect matching of G and the maximum weight of a matching of G. The parameter eta(G), introduced by Brazil & al. in Brazil et al. (2016), is defined as the minimum of such a ratio among all nonnegative edge weight assignments of G. In the present paper, we propose a way to compute a lower bound for the parameter eta(G), and we use it to prove that for every rational number q in the interval [0, 1] there exists a graph G such that eta(G) = q. Moreover, we further use the same method, in combination with some new arguments, to establish the value of eta for Prism graphs and Mobius Ladders. Finally, we improve known results for Blanusa Snarks B-1 and B-2 by determining the exact value of eta(B-1) and eta(B-2). (C) 2021 Elsevier B.V. All rights reserved.

2021 - On 3-Bisections in Cubic and Subcubic Graphs [Articolo su rivista]
Mattiolo, Davide; Mazzuoccolo, Giuseppe
abstract

A k-bisection of a graph is a partition of the vertices in two classes whose cardinalities differ of at most one and such that the subgraphs induced by each class are acyclic with all connected components of order at most k. Esperet, Tarsi and the second author proved in 2017 that every simple cubic graph admits a 3-bisection. Recently, Cui and Liu extended that result to the class of simple subcubic graphs. Their proof is an adaptation of the quite long proof of the cubic case to the subcubic one. Here, we propose an easier proof of a slightly stronger result. Indeed, starting from the result for simple cubic graphs, we prove the existence of a 3-bisection for all cubic graphs (also admitting parallel edges). Then we prove the same result for the larger class of subcubic graphs as an easy corollary.

2020 - An equivalent formulation of the Fan-Raspaud Conjecture and related problems [Articolo su rivista]
Mazzuoccolo, G; Zerafa, Jp
abstract

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 paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, 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. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridges.

2020 - Computational results and new bounds for the circular flow number of snarks [Articolo su rivista]
Goedgebeur, Jan; Mattiolo, Davide; Mazzuoccolo, Giuseppe
abstract

It is well known that the circular flow number of a bridgeless cubic graph can be computed in terms of certain partitions of its vertex set with prescribed properties. In the present paper, we first study some of these properties that turn out to be useful in order to make an efficient and practical implementation of an algorithm for the computation of the circular flow number of a bridgeless cubic graph. Using this procedure, we determine the circular flow number of all snarks on up to 36 vertices as well as the circular flow number of various famous snarks. After that, as combination of the use of this algorithm with new theoretical results, we present an infinite family of snarks of order 8k+2 whose circular flow numbers meet a general lower bound presented by Lukot'ka and Skoviera in 2008. In particular this answers a question proposed in their paper. Moreover, we improve the best known upper bound for the circular flow number of Goldberg snarks and we conjecture that this new upper bound is optimal. (C) 2020 Elsevier B.V. All rights reserved.

2020 - Normal edge‐colorings of cubic graphs [Articolo su rivista]
Mazzuoccolo, Giuseppe; Mkrtchyan, Vahan
abstract

A normal k-edge-coloring of a cubic graph is a proper edge-coloring with k colors having the additional property that when looking at the set of colors assigned to any edge e and the four edges adjacent to it, we have either exactly five distinct colors or exactly three distinct colors. We denote by chi N '(G) the smallest k, for which G admits a normal k-edge-coloring. Normal k-edge-colorings were introduced by Jaeger to study his well-known Petersen Coloring Conjecture. More precisely, it is known that proving chi N '(G)<= 5 for every bridgeless cubic graph is equivalent to proving the Petersen Coloring Conjecture and then it implies, among others, Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with chi N '(G)=7. In contrast, the known best general upper bound for chi N '(G) was 9. Here, we improve it by proving that chi N '(G)<= 7 for any simple cubic graph G, which is best possible. We obtain this result by proving the existence of specific nowhere zero Z22-flows in 4-edge-connected graphs.

2020 - Normal 5-edge-colorings of a family of Loupekhine snarks [Articolo su rivista]
Ferrarini, L.; Mazzuoccolo, G.; Mkrtchyan, V.
abstract

In a proper edge-coloring of a cubic graph an edge uv is called poor or rich, if the set of colors of the edges incident to u and v contains exactly three or five colors, respectively. An edge-coloring of a graph is normal, if any edge of the graph is either poor or rich. In this note, we show that some snarks constructed by using a method introduced by Loupekhine admit a normal edge-coloring with five colors. The existence of a Berge-Fulkerson Covering for a part of the snarks considered in this paper was recently proved by Manuel and Shanthi (2015). Since the existence of a normal edge-coloring with five colors implies the existence of a Berge-Fulkerson Covering, our main theorem can be viewed as a generalization of their result.

2020 - Normal 6-edge-colorings of some bridgeless cubic graphs [Articolo su rivista]
Mazzuoccolo, G; Mkrtchyan, V
abstract

In an edge-coloring (proper) of a cubic graph, an edge is poor or rich, if the set of colors assigned to the edge and the four edges adjacent it, has exactly three or exactly five distinct colors, respectively. An edge is normal in an edge-coloring if it is rich or poor in this coloring. A normal k-edge-coloring of a cubic graph is an edge-coloring with k colors such that each edge of the graph is normal. We denote by chi(N)'(G) the smallest k, for which G admits a normal k-edge-coloring. Normal edge-colorings were introduced by Jaeger in order to study his well-known Petersen Coloring Conjecture. It is known that proving chi(N)'(G) <= 5 for every bridgeless cubic graph is equivalent to proving Petersen Coloring Conjecture. Moreover, Jaeger was able to show that it implies classical conjectures like Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture. Recently, two of the authors were able to show that any simple cubic graph admits a normal 7-edge-coloring, and this result is best possible. In the present paper, we show that any claw-free bridgeless cubic graph, permutation snark, tree-like snark admits a normal 6-edge-coloring. Finally, we show that any bridgeless cubic graph G admits a 6-edge-coloring such that at least 7/9 . vertical bar E vertical bar edges of G are normal. (C) 2019 Elsevier B.V. All rights reserved.

2020 - REDUCTION OF THE BERGE-FULKERSON CONJECTURE TO CYCLICALLY 5-EDGE-CONNECTED SNARKS [Articolo su rivista]
Macajova, E; Mazzuoccolo, G
abstract

The Berge-Fulkerson conjecture, originally formulated in the language of mathematical programming, asserts that the edges of every bridgeless cubic (3-valent) graph can be covered with six perfect matchings in such a way that every edge is in exactly two of them. As with several other classical conjectures in graph theory, every counterexample to the Berge-Fulkerson conjecture must be a non-3-edge-colorable cubic graph. In contrast to Tutte's 5-flow conjecture and the cycle double conjecture, no nontrivial reduction is known for the Berge-Fulkerson conjecture. In the present paper, we prove that a possible minimum counterexample to the conjecture must be cyclically 5-edge-connected.

2019 - A family of multigraphs with large palette index [Articolo su rivista]
Avesani, M.; Bonisoli, A.; Mazzuoccolo, G.
abstract

Given a proper edge-coloring of a loopless multigraph, the palette of a vertex is defined as the set of colors of the edges which are incident with it. The palette index of a multigraph is defined as the minimum number of distinct palettes occurring among the vertices, taken over all proper edge-colorings of the multigraph itself. In this framework, the palette pseudograph of an edge-colored multigraph is defined in this paper and some of its properties are investigated. We show that these properties can be applied in a natural way in order to produce the first known family of multigraphs whose palette index is expressed in terms of the maximum degree by a quadratic polynomial. We also attempt an analysis of our result in connection with some related questions.

2019 - Colourings of cubic graphs inducing isomorphic monochromatic subgraphs [Articolo su rivista]
Abreu, Marién; Goedgebeur, Jan; Labbate, Domenico; Mazzuoccolo, Giuseppe
abstract

A k-bisection of a bridgeless cubic graph G is a 2-colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes (monochromatic components in what follows) have order at most k. Ban and Linial Conjectured that every bridgeless cubic graph admits a 2-bisection except for the Petersen graph. A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph G with |E (G)| equivalent to O (mod 2) has a 2-edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic. In this paper, we provide evidence of a strong relation of the conjectures of Ban-Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above-mentioned conjectures. Moreover, we prove Ban-Linial's Conjecture for cubic-cycle permutation graphs. As a by-product of studying 2-edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.

2019 - Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations [Articolo su rivista]
Rinaldi, G.; Mazzuoccolo, G.
abstract

Brualdi and Hollingsworth conjectured in Brualdi and Hollingsworth (1996) that in any complete graph K2n, n≥3, which is properly colored with 2n−1 colors, the edge set can be partitioned into n edge disjoint rainbow spanning trees (where a graph is said to be rainbow if its edges have distinct colors). Constantine (2002) strengthened this conjecture asking the rainbow spanning trees to be pairwise isomorphic. He also showed an example satisfying his conjecture for every 2n∈{2s:s≥3}∪{5⋅2s,s≥1}. Caughmann, Krussel and Mahoney (2017) recently showed a first infinite family of edge colorings for which the conjecture of Brualdi and Hollingsworth can be verified. In the present paper, we extend this result to all edge-colorings arising from cyclic 1-factorizations of K2n constructed by Hartman and Rosa (1985). Finally, we remark that our constructions permit to extend Constatine's result also to all 2n∈{2sd:s≥1,d>3odd}.

2018 - A note on 2-bisections of claw-free cubic graphs [Articolo su rivista]
Abreu, Marién; Goedgebeur, Jan; Labbate, Domenico; Mazzuoccolo, Giuseppe
abstract

A k-bisection of a bridgeless cubic graph G is a 2-colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes have order at most k. Ban and Linial conjectured that every bridgeless cubic graph admits a 2-bisection except for the Petersen graph. In this note, we prove Ban–Linial's conjecture for claw-free cubic graphs.

2018 - Cores, joins and the Fano-flow conjectures [Articolo su rivista]
Jin, Ligang; Eckhard, Steffen; Mazzuoccolo, Giuseppe
abstract

The Fan-Raspaud Conjecture states that every bridgeless cubic graph has three 1-factors with empty intersection. A weaker one than this conjecture is that every bridgeless cubic graph has two 1-factors and one join with empty intersection. Both of these two conjectures can be related to conjectures on Fano-flows. In this paper, we show that these two conjectures are equivalent to some statements on cores and weak cores of a bridgeless cubic graph. In particular, we prove that the Fan-Raspaud Conjecture is equivalent to a conjecture proposed in [E. Steffen, 1-factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015) 195–206]. Furthermore, we disprove a conjecture proposed in [G. Mazzuoccolo, New conjectures on perfect matchings in cubic graphs, Electron. Notes Discrete Math. 40 (2013) 235–238] and we propose a new version of it under a stronger connectivity assumption. The weak oddness of a cubic graph G is the minimum number of odd components (i.e., with an odd number of vertices) in the complement of a join of G. We obtain an upper bound of weak oddness in terms of weak cores, and thus an upper bound of oddness in terms of cores as a by-product.

2018 - Measures of edge-uncolorability of cubic graphs [Articolo su rivista]
Fiol, M. A.; Mazzuoccolo, G.; Steffen, E.
abstract

There are many hard conjectures in graph theory, like Tutte’s 5-flow conjecture, and the 5-cycle double cover conjecture, which would be true in general if they would be true for cubic graphs. Since most of them are trivially true for 3-edge-colorable cubic graphs, cubic graphs which are not 3-edge-colorable, often called snarks, play a key role in this context. Here, we survey parameters measuring how far apart a non 3-edge-colorable graph is from being 3-edge-colorable. We study their interrelation and prove some new results. Besides getting new insight into the structure of snarks, we show that such measures give partial results with respect to these important conjectures. The paper closes with a list of open problems and conjectures.

2017 - Flows and Bisections in Cubic Graphs [Articolo su rivista]
Esperet, L.; Mazzuoccolo, Giuseppe; Tarsi, M.
abstract

A k-weak bisection of a cubic graph G is a partition of the vertex-set of G into two parts V 1 and V 2 of equal size, such that each connected component of the subgraph of G induced by V i (i = 1, 2) is a tree of at most k − 2 vertices. This notion can be viewed as a relaxed version of nowhere-zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere-zero r-flow has a [r]-weak bisection. In this article, we study problems related to the existence of k-weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4-weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5-weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5-flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.

2017 - Nowhere-Zero 5-Flows On Cubic Graphs with Oddness 4 [Articolo su rivista]
Mazzuoccolo, Giuseppe; Steffen, Eckhard
abstract

Tutte’s 5-flow conjecture from 1954 states that every bridge- less graph has a nowhere-zero 5-flow. It suffices to prove the conjecture for cyclically 6-edge-connected cubic graphs. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. This implies that every minimum counterexample to the 5-flow conjecture has oddness at least 6.

2017 - On the palette index of a graph: the case of trees [Articolo su rivista]
Bonisoli, Arrigo; Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract

The palette of a vertex v of a graph G in a proper edge-coloring is the set of colors assigned to the edges which are incident with v. The palette index of G is the minimum number of palettes occurring among all proper edge-colorings of G. After reviewing some results on the palette index of regular graphs, we consider the problem of determining the palette index for non-regular graphs. We begin by considering the family of trees. We give an upper bound for the palette index of a tree in terms of the maximum degree Δ. We show that this bound is best possible by producing, for each Δ≥ 3, a tree T^ Δ whose palette index reaches the upper bound.

2016 - Edge-colorings of 4-regular graphs with the minimum number of palettes [Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, G.
abstract

A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Horňák, Kalinowski, Meszka and Woźniak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs.

2016 - On the equitable total chromatic number of cubic graphs [Articolo su rivista]
Dantas, S.; de Figueiredo, C. M. H.; Mazzuoccolo, Giuseppe; Preissmann, M.; dos Santos, V. F.; Sasaki, D.
abstract

A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. Wang conjectured that the equitable total chromatic number of a multigraph of maximum degree ΔΔ is at most Δ+2Δ+2, and proved this for the case where Δ≤3Δ≤3. Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5, and in this work we prove that the problem of deciding whether it is 4 is NP-complete for bipartite cubic graphs. Furthermore, we present the first known Type 1 cubic graphs with equitable total chromatic number 5. All of them have, by construction, a small girth. We also find one infinite family of Type 1 cubic graphs of girth 5 having equitable total chromatic number 4. This motivates the following question: Does there exist Type 1 cubic graphs of girth greater than 5 and equitable total chromatic number 5?

2016 - On the total coloring of generalized Petersen graphs [Articolo su rivista]
Dantas, S.; de Figueiredo, C. M. H.; Mazzuoccolo, Giuseppe; Preissmann, M.; dos Santos, V. F.; Sasaki, D.
abstract

We show that ‘‘almost all’’ generalized Petersen graphs have total chromatic number 4. More precisely: for each integer k ≥ 2, there exists an integer N (k) such that, for any n ≥ N (k) , the generalized Petersen graph G (n,k) has total chromatic number 4.

2016 - The structure of graphs with circular flow number 5 or more, and the complexity of their recognition problem [Articolo su rivista]
Esperet, Louis; Mazzuoccolo, Giuseppe; Tarsi, Michael
abstract

For some time the Petersen graph has been the only known Snark with circular flow number 5 (or more, as long as the assertion of Tutte’s 5-flow Conjecture is in doubt). Although infinitely many such snarks were presented eight years ago in [9], the variety of known methods to construct them and the structure of the obtained graphs were still rather limited. We start this article with an analysis of sets of flow values, which can be transferred through flow networks with the flow on each edge restricted to the open interval (1,4) modulo 5. All these sets are symmetric unions of open integer intervals in the ring ℝ/5ℤ. We use the results to design an arsenal of methods for constructing snarks S with circular flow number ϕc(S)≥5. As one indication to the diversity and density of the obtained family of graphs, we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete.

2016 - Treelike Snarks [Articolo su rivista]
Abreu, Marien; Kaiser, Tomas; Labbate, Domenico; Mazzuoccolo, Giuseppe
abstract

We study snarks whose edges cannot be covered by fewer than five perfect matchings. Esperet and Mazzuoccolo found an infinite family of such snarks, generalising an example provided by Hägglund. We construct another infinite family, arising from a generalisation in a different direction. The proof that this family has the requested property is computer-assisted. In addition, we prove that the snarks from this family (we call them treelike snarks) have circular flow number φ C (G) > 5 and admit a 5-cycle double cover.

2015 - Excessive [l,m]-factorizations [Articolo su rivista]
Cariolaro, David; Mazzuoccolo, Giuseppe
abstract

Given two positive integers l and m, with l≤m, an [l,m]-covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l≤;|M|≤m for every M. An [l,m]-covering M of G is an excessive [l,m]-factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive [l,m]-factorization of G (or ∞, if G does not admit an excessive [l,m]-factorization) is a graph parameter called the excessive [l,m]-index of G and denoted by χ[l,m]′(G). In this paper we study such parameter. Our main result is a general formula for the excessive [l,m]-index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes χ[l,m]′(G) for any fixed constants l and m and outputs an excessive [l,m]-factorization of G, whenever the latter exists.

2015 - On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph [Articolo su rivista]
Esperet, Louis; Mazzuoccolo, Giuseppe
abstract

A conjecture of Berge and Fulkerson (1971) states that every cubic bridgeless graph contains 6 perfect matchings covering each edge precisely twice, which easily implies that every cubic bridgeless graph has three perfect matchings with empty intersection (this weaker statement was conjectured by Fan and Raspaud in 1994). Let mt be the supremum of all reals α≤1 such that for every cubic bridgeless graph G, there exist t perfect matchings of G covering a fraction of at least α of the edges of G. It is known that the Berge-Fulkerson conjecture is equivalent to the statement that =1, and implies that =1415 and =45. In the first part of this paper, we show that m4=1415 implies =45, and =45 implies the Fan-Raspaud conjecture, strengthening a recent result of Tang, Zhang, and Zhu. In the second part of the paper, we prove that for any 2≤t≤4 and for any real τ lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) τ of the edges of a given cubic bridgeless graph can be covered by t perfect matching is an NP-complete problem.

2014 - On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings [Articolo su rivista]
Esperet, L.; Mazzuoccolo, Giuseppe
abstract

The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this article, we prove that deciding whether this number is at most four for a given cubic bridgeless graph is NP-complete. We also construct an infinite family F of snarks (cyclically 4-edge-connected cubic graphs of girth at least 5 and chromatic index 4) whose edge-set cannot be covered by four perfect matchings. Only two such graphs were known. It turns out that the family F also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with m edges has length at least 4m/3, and we show that this inequality is strict for graphs of F. We also construct the first known snark with no cycle cover of length less than 4m/3 + 2.

2014 - On the excessive [m]-index of a tree [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

The excessive [m]-index of a graph G, denoted by χ′[m](G), is the minimum number of matchings of size m needed to cover the edge-set of G. We set χ′[m](G) = ∞ if such a cover does not exist and we call a graph G[m]-coverable if its excessive [m]-index is finite. Obviously χ′[1](G) = |E(G)| and it is easy to prove for a [2]-coverable graph G that χ′[2](G) = max {χ′(G), ⌈|E(G)|/2⌉} holds, where χ′(G) denotes the chromatic index of G. The case m = 3 is completely solved in Cariolaro and Fu (2009) [4]. In this paper we prove a general formula for computing the excessive [4]-index of a tree and we conjecture a possible generalization for any value of m. Furthermore, we prove that such a formula does not work for the excessive [4]-index of an arbitrary graph.

2014 - Upper bounds for the automorphic chromatic index of a graph [Articolo su rivista]
Mazzuoccolo, G.; Ruini, Beatrice
abstract

The automorphic H-chromatic index of a graph G is the minimum integer m for which G has a proper edge-coloring with m colors preserved by a given subgroup H of the full automorphism group of G. We determine upper bounds for this index in terms of the chromatic index of G for some abelian 2-groups H.

2013 - An upper bound for the excessive index of an r-graph [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

We construct a family of r-graphs having a minimum 1-factor cover of cardinality 2r − 1 (disproving a conjecture of Bonisoli and Cariolaro,Birkhauser, Basel, 2007, 73–84). Furthermore, we show the equivalence between the statement that 2r − 1 is the best possible upper bound for the cardinality of a minimum 1-factor cover of an r-graph and the well-known generalized Berge–Fulkerson conjecture.

2013 - Covering a cubic graph with perfect matchings [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

Let G be a bridgeless cubic graph. A well-known conjecture of Berge and Fulkerson can be stated as follows: there exist five perfect matchings of G such that each edge of G is contained in at least one of them. Here, we prove that in each bridgeless cubic graph there exist five perfect matchings covering a portion of the edges at least equal to 215 231 . By a generalization of this result, we decrease the best known upper bound, expressed in terms of the size of the graph, for the number of perfect matchings needed to cover the edge-set of G.

2013 - Covering cubic graphs with matchings of large size [Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract

Let m be a positive integer and let G be a cubic graph of order 2n. We consider the problem of covering the edge-set of G with the minimum number of matchings of size m. This number is called the excessive [m]-index of G in the literature. The case m = n, that is, a covering with perfect matchings, is known to be strictly related to an outstanding conjecture of Berge and Fulkerson. In this paper we study in some detail the case m = n-1. We show how this parameter can be large for cubic graphs with low connectivity and we furnish some evidence that each cyclically 4-connected cubic graph of order 2n has excessive [n-1]-index at most 4. Finally, we discuss the relation between excessive [n-1]-index and some other graph parameters such as oddness and circumference.

2013 - Invariant Kekulé structures in fullerene graphs [Articolo su rivista]
Mathieu, Bogaerts; Giuseppe, Mazzuoccolo; Rinaldi, Gloria
abstract

Fullerene graphs are trivalent plane graphs with only hexagonal and pentagonal faces. They are often used to model large carbon molecules. A totally symmetric Kekule structure in a fullerene graph is a set of independent edges which is fixed by each automorphism of the fullerene. Starting from the complete catalog of all fullerenes with at least ten symmetries, we establish exactly which of them have at least one totally symmetric Kekule structure.

2013 - New conjectures on perfect matchings in cubic graphs [Relazione in Atti di Convegno]
Mazzuoccolo, Giuseppe
abstract

We propose three new conjectures on perfect matchings in cubic graphs. The weakest conjecture is implied by a well-known conjecture of Berge and Fulkerson. The other two conjectures are a strengthening of the first one. All conjectures are trivially verified for 3-edge-colorable cubic graphs and by computer for all snarks of order at most 34

2013 - Totally Symmetric Kekule structures in fullerene graphs with ten or more symmetries [Articolo su rivista]
M., Bogaerts; G., Mazzuoccolo; Rinaldi, Gloria
abstract

Graph Theoretic fullerenes are designed to model large carbon molecules: each vertex represents a carbon atom and the edges represent chemical bonds. A totally symmetric kekule structure in a fullerene graph is a set of independent edges which is fixed by all symmetries of the fullerene. It was recently suggested that molecules with totally symmetric kekule structures could have physical and chemical properties. Starting from a catalog given by J.Graver, we study all graph theoretic fullerenes with at least ten symmetries and we establish exaclty which of them have a totally symmetric kekule structure.

2011 - Cyclic and dihedral 1-factorizations of complete multipartite graphs [Articolo su rivista]
M., Bogaerts; Mazzuoccolo, Giuseppe
abstract

An automorphism group G of a 1-factorization of the complete multipartite graph Km×n consists of permutations of the vertices of the graph mapping factors to factors. In this paper, we give a complete answer to the existence problem of a 1-factorization of Km×n admitting a cyclic or dihedral group acting sharply transitively on the vertices of the graph.

2011 - Graphs of arbitrary excessive class [Articolo su rivista]
Mazzuoccolo, Giuseppe; M., Young
abstract

We show that there exists a family of r-regular graphs of arbitrarily large excessive index for each integer r greater than 3. Furthermore, we answer a question in Bonisoli and Cariolaro (2007) showing that all the positive integers can be attained as excessiveclasses of regular graphs.

2011 - Perfect one-factorizations in generalized Petersen graphs [Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract

A perfectly one-factorable (P1F) regular graph G is a graph admitting a partition of the edge-set into one-factors such that the union of any two of them is a Hamiltonian cycle. We consider cubic graphs. The existence of a P1F cubic graph is guaranteed for each admissible value of the number of vertices. We give conditions for determining P1F graphs within a subfamily of generalized Petersen graphs.

2011 - The equivalence of two conjectures of Berge and Fulkerson [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1-factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge-set of G can becovered with at most five 1-factors. We prove that the two conjectures are equivalent.

2010 - Abelian 1-factorizations in infinite graphs [Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract

For each finitely generated abelian group G, we construct a 1-factorization of the countable complete graph admitting G as an automorphism group acting sharply transitively on vertices.

2010 - Computing the automorphic chromatic index of certain snarks [Articolo su rivista]
Fiori, Carla; Mazzuoccolo, Giuseppe; Ruini, Beatrice
abstract

The automorphic H-chromatic index of agraph G is the minimum integer m for which G has aproper edge-coloring with m colors which is preserved by the fullautomorphism group H of G. We determine the automorphic H-chromatic index of eachmember of four infinite classes of snarks: type I Blanu\v{s}asnarks, type II Blanu\v{s}a snarks, Flower snarks and Goldbergsnarks.

2010 - On the automorphic chromatic index of a graph [Articolo su rivista]
Fiori, Carla; Mazzuoccolo, Giuseppe; Ruini, Beatrice
abstract

In this paper we define the automorphic H-chromatic index of agraph G as the minimum integer m for which G has aproper edge-coloring with m colors which is preserved by a given automorphism group H of G. After the description of some properties, we determine upper bounds for this indexwhen H is a cyclic group of prime order. We also show that these upper bounds are best possible in a number of istances.

2010 - Sharply transitive 1-factorizations of complete multipartite graphs [Articolo su rivista]
Mazzuoccolo, Giuseppe; Rinaldi, Gloria
abstract

Given a finite group G of even order, which graphs T have a 1-factorization admitting G as an automorphism group with a sharply transitive action on the vertex-set? Starting from this question we prove some general results and develop an exhustive analysis when T is a complete multipartite graph and G is cyclic.

2010 - The NP-completeness of automorphic colorings [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.

2009 - Automorphic chromatic index of generalized Petersen graphs [Articolo su rivista]
Mazzuoccolo, Giuseppe; Ruini, Beatrice
abstract

The automorphic A-chromatic index of agraph G is the minimum integer m for which G has aproper edge-coloring with m colors which is preserved by a givensubgroup A of the full automorphism group of G. We computethe automorphic A-chromatic index of each generalized Petersengraph when A is the full automorphism group.

2009 - On 2-factorizations of the complete graph: from the k-pyramidal to the universal property [Articolo su rivista]
Bonvicini, Simona; G., Mazzuoccolo; Rinaldi, Gloria
abstract

We consider 2-factorizations of complete graphs which possess an automorphism group fixing k\ge 0 vertices and acting sharply transitively on the others. We study the structures of such factorizations and consider the cases in which the group is either abelian or dihedral in somemore details. We prove that the class of 2-factorizations of complete graphs is universal. Namely each finite group is the full automorphism group of a 2-factorization of the class.

2009 - 3-regular matchstick graphs with given girth [Articolo su rivista]
S., Kurz; Mazzuoccolo, Giuseppe
abstract

We consider 3-regular planar matchstick graphs, i. e. those whichhave a planar embedding such that all edge lengths are equal, with given girth g. For girth 3 it is known that such graphs exist if and only if the number of vertices n is an even integer larger or equal to 8. Here we prove that such graphs exist for girth g = 4 if and only if n is even and at least 20. We provide an example for girth g = 5 consisting of 180 vertices.

2008 - On 2-factorizations whose automorphism group acts doubly transitively on the factors [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

Let F be a 2-factorization of the complete graph Kv admitting an automorphism group G acting doubly transitively on the set offactors. In the Hamiltonian case the only possibility is the unique factorization of K5, while in the non-Hamiltonian case we givesome classes of examples and some necessary conditions for the existence of such factorizations.

2008 - Perfect one-factorizations in line-graphs and planar graphs [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

2008 - Primitive 2-factorizations of the complete graph [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

Let F be a 2-factorization of the complete graph Kv admitting an automorphism group G acting primitively on the set of vertices.If F consists of Hamiltonian cycles, then F is the unique, up to isomorphisms, 2-factorization of Kpn admitting an automorphismgroup which acts 2-transitively on the vertex-set. In the non-Hamiltonian case we construct an infinite family of examples whose automorphism group does not contain a subgroup acting 2-transitively on vertices.

2008 - 2-fattorizzazioni del grafo completo con un prefissato gruppo di automorfismi [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

Sunto tesi di dottorato.

2007 - Doubly transitive 2-factorizations [Articolo su rivista]
Bonisoli, Arrigo; M., Buratti; Mazzuoccolo, Giuseppe
abstract

Let be a 2-factorization of the complete graph Kv admitting an automorphism group G acting doubly transitively on the set of vertices. The vertex-set V(Kv) can then be identified with the point-set of AG(n, p) and each 2-factor of is the union of p-cycles which are obtained from a parallel class of lines of AG(n, p) in a suitable manner, the group G being a subgroup of A G L(n, p) in this case. The proof relies on the classification of 2-(v, k, 1) designs admitting a doubly transitive automorphism group. The same conclusion holds even if G is only assumed to act doubly homogeneously.

2007 - k–Pyramidal One–Factorizations [Articolo su rivista]
Mazzuoccolo, Giuseppe; Rinaldi, Gloria
abstract

We consider one–factorizations of complete graphs which possess an automorphism group fixing k ≥ 0 vertices and acting regularly (i.e., sharply transitively) on the others. Since the cases k = 0 and k = 1 are well known in literature, we study the case k>=2 in some detail. We prove that both k and the order of the group are even and the group necessarily contains k − 1 involutions. Constructions for some classes of groups are given. In particular we extend the result of [7]: let G be an abelian group of even order and with k − 1 involutions, a one–factorization of a complete graph admitting G as an automorphism group fixing k vertices and acting regularly on the others can be constructed.

2006 - A new description of perfecly one-factorable cubic graphs [Articolo su rivista]
Bonvicini, Simona; G., Mazzuoccolo
abstract

A perfectly one-factorable (P1F) regular graph is a graph admitting a partition of the edge-set into one-factors such that the union of any two of them is a Hamiltonian cycle. The case of cubic graphs is treated. The existence of a P1F cubic graph is guaranteed for each admissible value of the number of vertices. A description of this class was obtained by Kotzigin 1962. It is the purpose of the present paper to produce an alternative proof of Kotzig's result.

2006 - A new description of perfectly one-factorable cubic graphs [Articolo su rivista]
S., Bonvicini; Mazzuoccolo, Giuseppe
abstract

A perfectly one-factorable (P1F) regular graph is a graph admitting a partition of the edge-set into one-factors such that the union of any two of them is a Hamiltonian cycle. The case of cubic graphs is treated. The existence of a P1F cubic graph is guaranteed for each admissible value of the number of vertices. A description of this class was obtained by Kotzig in 1962. It is the purpose of the present paper to produce an alternative proof of Kotzig’s result.

2006 - On perfectly one-factorable cubic graphs [Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract

We study cubic graphs possessing a perfect one–factorization.

2006 - On 2-factorizations with some symmetry [Articolo su rivista]
Mazzuoccolo, Giuseppe
abstract

We consider 2-factorizations of the complete graph Kv whose automorphism group is ”rich” in some sense. In particular we show the results obtained when the automorphism group acts 2-transitively either on the vertices of Kv or on the set of factors.