ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 115-124 https://doi.org/10.26493/1855-3974.1528.d41
(Also available at http://amc-journal.eu)
A family of multigraphs with large palette index
Maddalena Avesani
Dipartimento di Informática, Universita di Verona, Strada Le Grazie 15, Verona, Italy
Arrigo Bonisoli
Dipartimento di Scienze Fisiche, Informatiche e Matematiche, Universita di Modena e Reggio Emilia, Via Campi 213/b, Modena, Italy
Giuseppe Mazzuoccolo
Dipartimento di Informatica, Universita di Verona, Strada Le Grazie 15, Verona, Italy
Received 13 November 2017, accepted 1 April 2019, published online 25 August 2019
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.
Keywords: Palette index, edge-coloring, interval edge-coloring. Math. Subj. Class.: 05C15
1 Introduction
Generally speaking, as soon as a chromatic parameter for graphs is introduced, the first piece of information that is retrieved is whether some universal meaningful upper or lower bound holds for it. This circumstance is probably best exemplified by mentioning, say, Brooks' theorem for the chromatic number and Vizing's theorem for the chromatic index. In either instance the maximum degree A is involved and that probably explains the trend
E-mail addresses: maddalena.avesani@studenti.univr.it (Maddalena Avesani), arrigo.bonisoli@unimore.it (Arrigo Bonisoli), giuseppe.mazzuoccolo@univr.it (Giuseppe Mazzuoccolo)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
104
ArsMath. Contemp. 17 (2019) 115-114
to consider A as a somewhat natural parameter, in terms of which bounds for other chromatic parameters should be expressed. In the current paper we make no exception to this trend and use the maximum degree A as a reference value for the recently introduced chromatic parameter known as the palette index. To this purpose we introduce an additional tool, that we call the palette pseudograph, which can be defined from a given multigraph with a proper edge-coloring. Some properties of the palette pseudograph are investigated in Section 2 and we feel they might be of interest in their own right. In the current context, we use these properties in connection with an attempt of finding a polynomial upper bound in terms of A for the palette index of a multigraph with maximum degree A. As a consequence of our main construction in Section 3, we can assert that if such a polynomial bound exists at all then it must be at least quadratic.
Throughout the paper, following a standard terminology (see for instance [7]), we use the term multigraph to denote an undirected graph with multiple edges but no loops, while we use the term pseudograph for a graph admitting both multiple edges and loops. For any given multigraph G, we always denote by V(G) and E(G) the set of vertices and the set of edges of G, respectively. We further denote by Gs the underlying graph of G, that is the simple graph obtained from G by shrinking to a single edge any set of multiple edges joining two given vertices.
By a coloring of a multigraph G we always mean a proper edge-coloring of G. A coloring of G is thus a mapping c: E(G) ^ C, where C is a finite set whose elements are designated as colors, with the property that adjacent edges always receive distinct colors. We shall often say that (G, c) is a colored multigraph, meaning that c is a coloring of the multigraph G.
Given a colored multigraph (G, c), the palette Pc(x) of a vertex x of G is the set of colors that c assigns to the edges which are incident with x.
The palette index s(G) of a simple graph G is defined in [9] as the minimum number of distinct palettes occurring among the vertices, taken over all proper edge-colorings of the graph G. The definition can be extended verbatim to multigraphs. The exact value of the palette index is known for some classes of simple graphs.
•	A graph has palette index 1 if and only if it is a class 1 regular graph [9, Proposition 1].
•	A connected class 2 cubic graph has palette index 3 or 4 according as it does or it does not possess a perfect matching, respectively [9, Theorem 9].
•	If n is odd, n > 3 then s(Kn) is 3 or 4 depending on n = 3 or 1 (mod 4), respectively [9, Theorem 4].
•	The palette index of complete bipartite graphs was determined in [8] in many instances.
The quoted result for complete graphs shows that it is possible to find a family of graphs, for which the maximum degree can become arbitrarily large, and yet the palette index admits a constant upper bound, namely 4 in this case.
As it was remarked in [4], the fact that a class 2 regular graph of degree A always admits a (A + 1)-coloring forces A + 1 to be an upper bound for the palette index of such a graph (namely, A + 1 is the number of A-subsets of a (A + 1)-set of colors).
That is definitely not the case for non-regular graphs: it was shown in [3] that for each positive integer A there exists a tree with maximum degree A whose palette index grows asymptotically as Aln(A).
M. Avesani et al.: A family of multigraphs with large palette index
117
Consequently, one cannot expect for the palette index any analogue of, say, Vizing's theorem for the chromatic index: the palette index of graphs of maximum degree A cannot admit a linear polynomial in A as a universal upper bound.
It is the main purpose of the present paper to produce an infinite family of multigraphs, whose palette index grows asymptotically as A2, see Section 3. Our method relies essentially on a tool that we define in Section 2, namely the palette pseudograph of a colored multigraph. This concept is strictly related to the notion of palette index and it appears to yield a somewhat natural approach to the study of this chromatic parameter.
2 The palette pseudograph of a colored multigraph
For any given finite set X and positive integer t we denote by t • X the multiset in which each element of X is repeated t times.
The next definition will play a crucial role for our construction in Section 3. Given a colored multigraph (G, c), we define its palette pseudograph rc(G) as follows.
The vertex-set of rc(G) is V(rc(G)) = {Pc(v) : v e V(g)}. In other words the vertices of rc(G) are all pairwise distinct palettes of (G, c).
For any given pair of adjacent vertices x and y of G, we declare the (not necessarily distinct) palettes Pc(x) and Pc(y) to be adjacent and define the corresponding edge in the palette pseudograph rc(G).
More precisely, if x and y are adjacent vertices in G such that their palettes Pc(x) and Pc(y) are distinct, then Pc(x) and Pc(y) yield two distinct vertices connected by an ordinary edge in the palette pseudograph rc(G), see vertices xi and x2 in Figure 1. If, instead, x and y are adjacent vertices in G with equal palettes Pc(x) and Pc(y), these form a single vertex with a loop in the palette pseudograph rc(G), see vertices x2 and x3 in Figure 1.
If two (equal or unequal) palettes appear on several pairs of adjacent vertices of G, then each such pair yields one edge in rc(G) (either a loop or an ordinary edge). It is thus quite possible that the palette pseudograph rc(G) presents multiple (ordinary) edges between two given distinct vertices as well as multiple loops at a given vertex.
An example of a pair (G, c) and the corresponding palette pseudograph rc(G) is presented in Figure 1.
The number of vertices of the palette pseudograph rc(G) is thus equal to the number of distinct palettes in the colored multigraph (G, c), while the number of edges (loops and ordinary edges) in rc(G) is equal to the number of edges in the underlying simple graph Gs.
The following proposition is also an easy consequence of the definition of the palette pseudograph: note that each loop in rc(G) contributes 2 to the degree of its vertex.
Proposition 2.1. For any given colored multigraph (G, c), the degree of a vertex Pc(x) in the palette pseudograph rc(G) is equal to the sum of the degrees in the underlying simple graph Gs of all vertices whose palettes in (G, c) are equal to Pc(x).
3 The main construction
The main purpose of this Section is the construction of a multigraph GA with maximum degree A, whose palette index is expressed by a quadratic polynomial in A.
For the sake of brevity we shall assume A even, A > 2: a slight modification of our
104
ArsMath. Contemp. 17 (2019) 118-114

X5
1
X1
2*1
4#51
x4

2
X3
{1,4}
{1,2}
{1,2,3,5} {1,3,4,5}
Figure 1: A multigraph G with a proper edge-colouring and the associated palette pseudograph.
construction yields the same result for odd values of A. Even though our graph GA is not connected, a connected example can easily be obtained from GA as follows. Introduce a new vertex to which js declared to be adjacent to each vertex of degree A in GA. The resulting multigraph GA is connected with maximum degree A + 1. The palette index of the multigraphs GA is again bounded from below by a quadratic polynomial in A. We feel appropriate at this stage to stress a peculiar property of the palette index, in comparison with other chromatic parameters: it is not true in general that the palette index of a multigraph is equal to the maximum of the palette indices of its connected components (see Proposition 3 in [4]). This says that there is no particular reason to prefer connected examples to disconnected ones in this context.
The multigraph GA is obtained as the disjoint union of multigraphs HtA, for t = 1,2,..., A - 2, which are defined as follows.
Let HA be the simple graph with vertices u, v
0 v1,
vA 1 and edges uv0, uv
a —1 0 1 2 3
uvA 1,v0v1,v2v3
,vA-2vA-
1
1. The graph HA is sometimes called a windmill graph [6] and can also be described as being obtained from the wheel WA (see [2]) by alternately deleting edges on the outer cycle.
The multigraph HtA is obtained by replacing each edge vj vj+1 which is not incident with the central vertex u with t parallel edges between the same vertices vj and vj+1. In detail, define for t =1,2,..., A - 2
V (HA) = {ut ,v0,v!, E(HA) = t -{vjvj+1
,v
a
-1}
j e {0, 2,4,
, A - 2}}U{utvj : j e {0,1, 2,..., A - 1}}
ha
(V (HA),E (Hf))
For j =0,1,..., A -1 we denote the edge utvj by ej or simply by ej once t is understood. Furthermore, for any index j e {0,1,..., A - 1} there is a uniquely determined index j' e {0,1,..., A - 1}, j = j' such that vj is the unique vertex, other than ut, which is adjacent to v\
in HA
The submultigraph of HtA which is induced by the vertices ut, vj, vj will be denoted
2
1
2
1
4
1
M. Avesani et al.: A family of multigraphs with large palette index
119
by L j. The edges of L j are ej, ej and the t repeated edges having vj and vj as endver-tices. By definition, we have Lj = Lj .
7
2
V
V
6
3
V
V
Figure 2: The graph Hf.
We now assume that a k-edge-coloring c: E(HtA) ^ C = {c0, c1,..., ck-1} is given and study some properties of the palette pseudograph rc(HtA). Since the central vertex ut has degree A in HtA we have A < k and may assume, with no loss of generality, that c(ej) = cj holds for j = 0,1,..., A - 1. The inequality t < A - 2 yields in turn t + 1 < A. Consequently, since each non central vertex vj has degree t + 1, we see that the palette Pc(ut) = {0,1,..., A - 1} is distinct from every other palette Pc(vj). For that reason, rather than looking at the palette pseudograph rc(HtA) we consider the subpseudograph r-(HtA) = rc(HtA) \ Pc(ut) obtained by removing the palette Pc(ut) (as a vertex of the palette pseudograph).
Lemma 3.1. The pseudograph r- (HtA) is a simple graph and is a forest.
Proof. We prove first of all that T-(fftA) has no loop, that is Pc(vj) = Pc(vj ) for all j. Consider the two adjacent vertices vj and vj . The corresponding edges ej and ej have distinct colors cj and cj> in {0,..., A - 1}, respectively. The color cj cannot appear on one of the edges between vj and vj , since c is a proper coloring. Hence, cj belongs to Pc(vj) and does not belong to Pc(vj ), and the two palettes are distinct, as claimed.
Next, we prove that r-(HtA) has no multiple edges, by showing that if Pc(vj) = Pc(vh) for h = j, j', then Pc(vj ) = Pc(vh ). Suppose the vertices vj and vh share the same palette. The edges ej and eh are colored with colors cj and ch, respectively. Hence {cj, ch} c Pc(vj) (= Pc(vh)). In particular, one of the edges between v'h and vth has color cj and so we have cj g Pc(vth ). On the other hand, cj does not belong to Pc(vj ) because c is a proper coloring, and the claim follows.
In order to complete our proof, we need to prove that r- (HtA) has no cycle and is thus a forest.
Assume, by contradiction, that r-(HtA) has a cycle r. Without loss of generality, we may assume that r contains the vertices Pc(v°) and Pc(vi1) of r-(HtA). Since Pc(v°) has degree at least two in r- (HtA), there exists h = 0 such that Pc(v°) = Pc(vh) and Pc(vth ) belongs to r. Recall that e0 has colour c0 in c. Therefore, the colour c0 belongs to both
120
Ars Math. Contemp. 17 (2019) 153-183
palettes Pc (v0) and Pc(vh), since they are the same palette. Furthermore, the edge eh has colour ch, different from c0. Then c0 is the colour of one of the edges between vh and vh . Hence, the colour c0 also belongs to the palette Pc(v^ ). Repeating the same argument, we obtain that c0 belongs to each palette of the cycle r. That is a contradiction, since c0 does not belong to the palette Pc ( v^ ).	□
Lemma 3.2. The degree of a vertex Pc(vj) in Tc (HtA) is exactly equal to the number of vertices of HtA having the same palette Pc(vj) in the colouring c.
Proof. The underlying simple graph of HtA \ {ut} is the disjoint union of isolated edges, that is every vertex has degree exactly 1 in the underlying simple graph. It follows from Proposition 2.1 that when a given palette P is viewed as a vertex in r-(HtA), then its degree is equal to the number of vertices in HtA sharing the palette P.	□
The next Proposition states a well-known property of forests.
Proposition 3.3. The average degree of a forest is strictly less than 2.
Proof. Suppose that the forest F has n vertices. Then F has at most n — 1 edges and
]T d(v) = 2|E(F)|< 2(n — 1)
vev (F )
so that the average degree is
1 y d(v) < 2(n —1) < 2.	□
n ^ ' ~ n
vev (F )
By the previous proposition and Lemma 3.2, the average number of vertices in HtA sharing the same palette is less than 2 and that implies the following lower bound for the palette index of HtA:
KhA) > A +1.
Theorem 3.4.
A (A — 2) < s(GA) < (A+1)(A — 2)	(3.1)
Proof. The second inequality is an immediate consequence of the fact that the number of vertices in GA is (A + 1) (A - 2).
For the first inequality, it is sufficient to observe that all vertices of degree t + 1 in GA belong to the subgraph HtA, so they cannot share the same palette with a vertex in another subgraph HtA, with t' = t. On the other hand, the vertex ut of degree A in HtA could share the same palette with every other vertex of degree A, one in each subgraph HtA. We obtain
S(GA) > (Ha) - 1) > (A - 2)A.	□
M. Avesani et al.: A family of multigraphs with large palette index
121
4 Some considerations on a related parameter
We introduce a new natural parameter related to the palette index of a multigraph. Consider an edge-coloring c of G which minimizes the number of palettes, that is the number of palettes is exactly s(G): how many colors does c require? More precisely, we consider the minimum k such that there exists a k-edge-coloring of G with s(G) palettes. We will denote such a minimum by x?(G). Obviously, x?(G) > x'(G) because we need at least the number of colors in a proper edge-coloring. In [9], the authors remark that in some cases this number is strictly larger than the chromatic index of the graph. How much larger could it be?
An upper bound for the value of x? (G) for some classes of graphs can be deduced from an analysis of the proofs of the corresponding results for the palette index.
•	[9] Let Kn be a complete graph with n > 1 vertices. Then,
X?(K„) = A if n = 0 (mod 2) 3A
X?(Kn) < — if n = 1 (mod 2)
In particular, if n = 4k + 3 then it is proved that the palette index is equal to 3 and the proof is obtained by using three sets of colors of cardinality 2k +1. If n = 4k + 5, the proof works by using three sets of colors of cardinality 2k + 1 and three additional colors, that is 6(k + 1) colors. The number of colors is exactly 3r in both cases.
•	[9] Let G be a cubic graph. Then,
X?(G) < 5.
In particular, five colors are necessary if G is not 3-edge-colorable and has no perfect matching.
•	[4] Let G be a 4-regular graph. Then,
X?(G) < 6.
In particular, six colors are used in some examples with palette index 3 (see the proof of Proposition 11 in [4]).
•	[3] Let G be a forest. Then,
X?(G) = A.
•	[8] Let Km,n be a complete bipartite graph with 1 < m < n. This situation is a little more involved, in the sense that we cannot always obtain a good upper bound for Xs(Km,n) using the proofs of the results in [8]. In some cases, see for instance Proposition 11 in [8], the number of colors is twice the maximum degree A (recall that minimizing the number of colors was not important in that context). Nevertheless, we analyze some small cases and obtain the same number of palettes (the minimum) by using a smaller number of colors.
One such example is obtained by considering the graph K5,6 (i.e. case k = 3 in Proposition 11 of [8]). Denote by {u1,..., u5} and {v1;..., v6} the bipartition of the vertex-set of K5 6. The proof of Proposition 11 in [8] furnishes an edge-coloring
122
Ars Math. Contemp. 17 (2019) 153-183
with 12 colors and 6 palettes. Following the notation used in [8] we represent the coloring with a matrix, where the element in position (i,j) is the color of the edge
M>
1	2	3	4	5	6
3	1	2	6	4	5
2	3	1	5	6	4
7	8	9	10	11	12
8	7	12	11	10	9
5,6
The following coloring has only 8 colors and again 6 palettes.
/1 2 3 4 5 6\
M
5,6
3	1	2	6	4 5 2	3	1	5	6 4
4	5	7	8	1	2 \5	4	8	7	2 1/
We would like to stress that, even if we can obtain similar colorings for some other sporadic cases, we are not able to generalize our results to all infinite families considered in [8].
All previous results and the study of some sporadic cases suggest that x'(G) cannot be too large with respect to A. In particular, we believe there exists a linear upper bound for x'(G) in terms of A. The following is thus an even stronger conjecture.
Conjecture 4.1. Let G be a (simple) graph. Then,
3
x'(G) < r2AT-
As far as we know, this conjecture is new and completely open. We believe any progress in that direction could be useful for a deeper understanding of the behavior of the palette index of general graphs.
UiV

5 Concluding remarks and open problems
In this final Section we propose some further open questions and indicate a few connections with other known problems.
In Section 3, we have presented a family of multigraphs whose palette index is expressed by a quadratic polynomial in A. We were not able to find a family of simple graphs with such a property and so we leave the existence of such a family as an open problem.
Problem 5.1. For A = 3,4,..., does there exist a simple graph with maximum degree A whose palette index is quadratic in A?
As far as we know, the best general upper bound in terms of A for the palette index of a simple graph G is the trivial one, which is obtained from a (A + 1)-edge-colouring c of G: in principle, each non-empty proper subset of the set of colours could occur as a palette of (G, c), whence s(G) < 2A+1 - 2. On the other hand, all known examples suggest that this upper bound is far from being tight. In particular, we raise the question whether a polynomial upper bound holding for general multigraphs may exist at all.
M. Avesani et al.: A family of multigraphs with large palette index
123
Problem 5.2. Prove the existence of a polynomial p(A) such that s(G) < p(A) for every multigraph G with maximum degree A.
We slightly suspect that if a polynomial p solving Problem 5.2 can be found at all, then some quadratic polynomial will do as well.
Finally, we would like to stress how this kind of problems on the palette index is somehow related to another well-known type of edge-colorings, namely interval edge-colorings, introduced by Asratian and Kamalian in [1].
Definition 5.3. A proper edge-coloring c of a graph with colors {c1; c2,..., ct} is called an interval edge-colouring if all colours are actually used, and the palette of each vertex is an interval of consecutive colors.
The following relaxed version of the previous concept was first studied in [10] and then explicitly introduced in [5].
Definition 5.4. A proper edge-colouring c of a graph with colors {c1; c2,..., ct} is called an interval cyclic edge-colouring if all colours are used and the palette of each vertex is either an interval of consecutive colors or its complement.
Both interval and interval cyclic edge-colorings are thus proper edge-colourings with severe restrictions on the set of admissible palettes.
There are many more results on interval edge-colourings (see among others [12]). In particular, it is known that not all graphs admit an interval edge-colouring. Furthermore, it is proved in [11] that if a multigraph of maximum degree A admits an interval edge-colouring then it also admits an interval cyclic A-edge-colouring. The following holds:
Proposition 5.5. Let G be a multigraph of maximum degree A admitting an interval edge-colouring. Then, s(G) < A2 — A + 1.
Proof. Since G admits an interval edge-colouring, then it also admits an interval cyclic A-edge-colouring c (see [11]). Each palette of (G, c) is thus an interval of colors in the set {c1; c2,..., cA} or its complement is one such interval. For t = 1,..., A — 1, there are exactly A such subsets of cardinality t, and a unique one for t = A. We have thus at most A(A — 1) + 1 distinct palettes in (G, c), that is s(G) < A2 — A + 1.	□
In other words, the previous Proposition assures that a putative example of a family of multigraphs whose palette index grows more than quadratically in A should be searched for within the class of multigraphs without an interval edge-colouring.
In this paper, we also introduce the palette pseudograph of a colored multigraph (G, c). A precise characterization of the palette pseudograph of the family introduced in Section 3 is the key point of our main proof. It suggests that a study of palette pseudographs in a general setting could increase our knowledge of the palette index. Possibly, it could also help in the search for an answer to some of the previous problems. Hence, we conclude our paper with the following:
Problem 5.6. Let H be a pseudograph. Determine whether a colored multigraph (G, c) exists, such that H is the palette pseudograph of (G, c).
124
Ars Math. Contemp. 17 (2019) 153-183
References
[1]	A. S. Asratian and R. R. Kamalian, Interval colorings of the edges of a multigraph, in: R. N. Tonoyan (ed.), Applied Mathematics 5, Yerevan State University, Yerevan, pp. 25-34, 1987.
[2]	J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5.
[3]	A. Bonisoli, S. Bonvicini and G. Mazzuoccolo, On the palette index of a graph: the case of trees, in: D. Labbate (ed.), Selected Topics in Graph Theory and Its Applications, Seminario Interdisciplinare di Matematica (S.I.M.), Potenza, volume 14 of Lecture Notes of Seminario Interdisciplinare di Matematica, pp. 49-55, 2017.
[4]	S. Bonvicini and G. Mazzuoccolo, Edge-colorings of 4-regular graphs with the minimum number of palettes, Graphs Combin. 32 (2016), 1293-1311, doi:10.1007/s00373-015-1658-7.
[5]	D. de Werra and Ph. Solot, Compact cylindrical chromatic scheduling, SIAM J. Discrete Math. 4 (1991), 528-534, doi:10.1137/0404046.
[6]	J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2016), #DS6, https: //www.combinatorics.org/files/Surveys/ds6/ds6v19-2016.pdf.
[7]	D. A. Holton and J. Sheehan, The Petersen Graph, volume 7 of Australian Mathematical Society Lecture Series, Cambridge University Press, Cambridge, 1993, doi:10.1017/ cbo9780511662058.
[8]	M. Hornak and J. Hudak, On the palette index of complete bipartite graphs, Discuss. Math. Graph Theory 38 (2018), 463-476, doi:10.7151/dmgt.2015.
[9]	M. Hornak, R. Kalinowski, M. Meszka and M. Wozniak, Minimum number of palettes in edge colorings, Graphs Combin. 30 (2014), 619-626, doi:10.1007/s00373-013-1298-8.
[10]	A. Kotzig, 1-factorizations of Cartesian products of regular graphs, J. Graph Theory 3 (1979), 23-34, doi:10.1002/jgt.3190030104.
[11]	A. Nadolski, Compact cyclic edge-colorings of graphs, Discrete Math. 308 (2008), 2407-2417, doi:10.1016/j.disc.2006.09.058.
[12]	P. A. Petrosyan and S. T. Mkhitaryan, Interval cyclic edge-colorings of graphs, Discrete Math. 339 (2016), 1848-1860, doi:10.1016/j.disc.2016.01.023.