A Note on the upper bound of the palette index of nearly bipartite graphs



Given a proper edge coloring α of a graph G, we define the palette S_G (v,α) of a vertex v ∈ V (G) as the set of all colors appearing on edges incident with v. The palette index s ̌(G) of G is the minimum number of distinct palettes occurring in a proper edge coloring of G. A graph G is called nearly bipartite if there exists v ∈ V (G) so that G-v is a bipartite graph. In this paper, we give an upper bound on the palette index of a nearly bipartite graph G by using the decomposition of G into cycles.

Keywords: edge coloring, proper edge coloring, palette, palette index.

Throughout this paper, a graph always means a finite undirected graph without loops, parallel edges and does not contain isolated vertices. Let and denote the sets of vertices and edges of a graph , respectively. The degree of a vertex in is denoted by , and the maximum degree of vertices in

by . The terms and concepts that we do not define can be found in [1].

An edge coloring of a graph is an assignment of colors to the edges of : it is proper if adjacent edges receive distinct colors. The minimum number of colors required in a proper edge coloring of a graph is called the chromatic index of and denoted by . By Vizing’s theorem [9], the chromatic index of equals either or . A graph with

is called Class 1 , while a graph with is called Class 2 .

In this paper we consider a chromatic parameter called the palette index of a simple graph . A proper edge-coloring of a graph defines at each vertex the set of colors of its incident edges. That set is called the palette of v and denoted by . The minimum number of palettes taken over all possible proper edge colorings of a graph is called palette index of a graph and denoted by [2]. Proper edge colorings with the minimum number of distinct palettes were studied for the first time in 2014, by Hornak, Kalinowski, Meszka, and Wozniak [2]. They determined the palette index of complete graphs. Namely,

Moreover, they also showed that the palette index of a d-regular graph is

if and only if the graph is . If is -regular and , then Vizing’s edge coloring theorem [9] implies that , and the case is not possible, as proved in [2]. There are few results about the palette index of non-regular graphs. Vizing’s edge coloring theorem also yields an upper bound on the palette index of a graph with maximum degree and without isolated vertices, mainly . In [6], Casselgren and Petrosyan provided an improvement and derived the following upper bound on the palette index of bipartite graphs:

where is the set of all odd degrees in and is the set of even degrees in .

In [3], Bonvicini and Mazzuoccolo proved that if is -regular and of , then , and that all these values are in fact attainable. Although it is possible to determine the exact value of the palette index for some classes of graphs, in general it is NP-complete problem, because from [4] it is known that computing the chromatic index of a given graph is a NP-complete problem. Next, we need some additional definitions.

Definition 1. (Edge subdivision). Let be a graph. The edge subdivision operation for an edge is the deletion of from and the addition of two new edges and along with the new vertex . This operation generates a new graph , where .

Definition 2. (Nearly bipartite). A graph

is called nearly bipartite if there exists so that is a bipartite graph.

We also need a classic result from factor theory, proof of which can be found in [10].

Theorem 1. (Petersen’s Theorem). Let be a -regular multigraph (where loops are allowed). Then has a decomposition into edge-disjoint -factors.

For a graph , denote by

the set of all degrees in , by the set of all odd degrees in , and by the set of even degrees in , respectively.

Theorem 2. If is an even nearly bipartite graph, then

Moreover, this upper bound is sharp for any odd length cycle.

Proof. In the proof of this theorem, we follow the idea from [6] (Theorem 2.2). We first construct a new multigraph as follows: for each vertex of degree , we add loops at . Clearly, is a -regular multigraph. Then, by Theorem 1, can be represented as a union of edge-disjoint 2-factors . By removing all loops from 2-factors

of , we obtain that the resulting graph G is a union of edge-disjoint even subgraphs . Note that for each , is a collection of cycles. Because is nearly bipartite, so that is a bipartite graph, therefore for any cycle from if then the length of that cycle is even. Clearly,

, hence belongs to at most odd cycles. By using the edge subdivision operation on edges incident with and belonging to the distinct cycles, we will construct a new graph that can be represented as a union of edge-disjoint even subgraphs . For each , is a collection of even cycles in , so we can properly color the edges of alternately with colors

and . As a result, the obtained coloring is a proper edge coloring of with colors . Now, if and , then there are even subgraphs such that , and thus . This means that for vertices

with , we have at most distinct palettes in the coloring and thus . Let us now consider t graph . If and is not one of the subdivided edges (the number of subdivided edges is at most ), then we can keep the color applied by and add at most new colors to the remaining ones, creating at most

new palettes in .

Hence,

Now, if contains a vertex with degree , it means that and the proof of the theorem is complete. But if there are no vertices with degree , then and

. In the resulting inequality, we take into account extra palettes that can be removed because the graph does not contain any vertices of degree .

From a given nearly bipartite graph G, we can construct an even super graph G' which can be represented as a union of edge-disjoint 2-factors. Let us first construct a new graph G' as defined in [6] by taking two vertex-disjoint copies and of and for every odd degree vertex of joining it by an edge with its copy in

. Since is a nearly bipartite graph, such that is bipartite graph, therefore is bipartite too, where is a copy of . Clearly, and . Using the same method as in the proof of the previous theorem, we obtain that vertices and belong to at most

odd cycles. Again, as in the proof of Theorem 2, using the edge subdivision operation on at most edges incident with or that belong to the distinct cycles, we will construct a graph . By applying the preceding proposition to , we immediately obtain the following.

Corollary 1 . For any nearly bipartite graph G, we have

Proof. Consider the graph defined above, and a proper edge coloring

of as described in the proof of Theorem 2. For each palette in , where , there are at most possible palettes in the restriction of to . Now by switching back from to the graph which is the copy of we will create at most

new palettes. So we can obtain a general upper bound for nearly bipartite graphs.

Corollary 2. For any nearly bipartite graph G, we have

Conclusion

In the current article, we examined the palette index of nearly bipartite graphs. We improved the upper bound of the palette index of an even nearly bipartite graph. Moreover, we showed that the upper bound is sharp for any odd length cycle. Also, we obtained the upper bound for any nearly bipartite graph as a corollary from this result.

References:

1. West D. B. / Introduction to Graph Theory / D. B. West. —: N.J.: Prentice-Hall, 2001.
2. M. Hornak, R. Kalinowski, M. Meszka, M. Wozniak. / Minimum Number of Palettes in Edge Colorings // Graphs and Combinatorics. — 2014. — № 30. — С. 619–626.
3. S. Bonvicini, G. Mazzuoccolo / Edge-Colorings of 4-Regular Graphs with the Minimum Number of Palettes // Graphs and Combinatorics. — 2016. — № 32. — С. 1293–1311.
4. I. Holyer / The NP-Completeness of Edge-Coloring / SIAM Journal on Computing. — 1981. — С. 718–720.
5. M. Avesani, A. Bonisoli, G. Mazzuoccolo. / A Family of Multigraphs with Large Palette Index // Ars Mathematica Contemporanea. — 2019. — № 17. — С. 115–124.
6. C. J. Casselgren, P. A. Petrosyan. / Some results on the palette index of graphs // Discrete Mathematics and Theoretical Computer Science.
7. S. Fiorini, R. J. Wilson / Edge-Colorings of Graphs // Research Notes in Mathematics.
8. R. Hammack, W. Imrich, S. Klavzar / Handbook of Product Graphs Second Edition // CRC Press. — 2011.
9. Vizing, V. G. / On an estimate of the chromatic class of a p-graph // Diskret. Analiz 3. — 1964. С. 25–30.