Graphs with large palette index

DOI10.1016/J.DISC.2022.112814MaRDI QIDQ2113372zbMATH OpenOpenAlexFDO

Authors Davide Mattiolo, G. Mazzuoccolo, G. Tabarelli

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.03827

zbMATH Keywords

edge-coloring palette index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

Review text

Let \(G=(V, E)\) be a simple connected graph. An edge-coloring of \(G\) is a map that assigns colors to the edges of \(G\) such that two incident edges obtain different colors. The minimum number of colors required in an edge-coloring of a graph \(G\) is called the chromatic index of \(G\). The palette of a vertex \(u \in V(G)\) with respect to the edge-coloring of \(G\) is the set of colors assigned to the edges incident to \(u\). Introduced in [\textit{M. Horňák} et al., Graphs Comb. 30, No. 3, 619--626 (2014; Zbl 1291.05066)] the palette index of a graph \(G\) is the minimum number of distinct palettes occurring in an edge-coloring of \(G\). Note that the chromatic index of an \(r\)-regular graph equals either \(r\) or \(r+1\). Obviously, the chromatic index of an \(r\)-regular graph is \(r\) if and only if its palette index is one. The paper considers the question about the existence of an \(r\)-regular graph with the (maximum possible) palette index \(r+1\). In order to (partially) answer this question, the authors provide the result that shows that a graph \(G\) which does not admit a spanning subgraph with all vertices of even degree and without isolated vertices admits the palette index that exceeds the minimum vertex degree of \(G\). For an odd \(r\), this result allows a construction of a family of \(r\)-regular graphs having palette index equal to \(r + 1\). The paper concludes with a description of a family of graphs whose palette index grows quadratically with respect to their maximum degree.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Graphs with large palette index

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2113372)