Edge-colorings of 4-regular graphs with the minimum number of palettes (Q2631073)

Every proper edge-coloring of a graph \(G\) induces for each vertex \(v\) a palette of colors, that is, the set of colors used on the edges incident to \(v\). The authors study the palette index \(\check{s}(G)\) of a graph \(G\), defined as the minimum number of distinct palettes taken over all proper edge-colorings of \(G\), a parameter introduced in [\textit{M. Horňák} et al., Graphs Comb. 30, No. 3, 619--626 (2014; Zbl 1291.05066)]. Since the chromatic index of any graph \(G\) with maximum degree \(\Delta(G)\) is either \(\Delta(G)\) or \(\Delta(G)+1\), the inequalities \(1\leq\check{s}(G)\leq d+1\) hold for every \(d\)-regular graph \(G\), with \(\check{s}(G)=1\) if and only \(G\) is class 1. Moreover, it was proved in the above-mentionned paper that the palette index of a regular graph is different from 2. Therefore, \(3\leq\check{s}(G)\leq d+1\) whenever \(G\) is a class 2 \(d\)-regular graph. A natural question is then to determine whether this upper bound is tight or not for every \(d\). The answer is positive when \(d=2\) or \(3\), as an odd cycle and a cubic graph with no perfect matching clearly have palette index 3 and 4, respectively. In this paper, the authors prove that the answer to this question is positive for \(d=4\). They also study \(4\)-regular graphs with palette index 3 or 4.