Graphs with large palette index (Q2113372)

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.