On Regal Colorings of Graphs

For a positive integer \( k \), let \( \mathcal{P}^*([k]) \) be the set of nonempty subsets of the set \( [k] = \{1, 2, \ldots, k\} \). For a connected graph \( G \) of order 3 or more, let \( c: E(G) \to \mathcal{P}^*([k]) \) be an edge coloring of \( G \) where adjacent edges may be colored the same. The induced vertex coloring \( c’: V(G) \to \mathcal{P}^*([k]) \) is defined by \( c'(v) = \bigcap_{e \in E_v} c(e) \), where \( E_v \) is the set of edges incident with \( v \). If \( c’ \) is a proper vertex coloring of \( G \), then \( c \) is called a regal \( k \)-edge coloring of \( G \). The minimum positive integer \( k \) for which a graph \( G \) has a regal \( k \)-edge coloring is the regal index \( \text{reg}(G) \) of \( G \). If \( c’ \) is vertex-distinguishing, then \( c \) is a strong regal \( k \)-edge coloring of \( G \). The minimum positive integer \( k \) for which \( G \) has a strong regal \( k \)-edge coloring is the strong regal index \( \text{sreg}(G) \) of \( G \). A brief survey of known results and conjectures on strong regal indexes of graphs is presented. The relationships between the regal index \( \text{reg}(G) \) and the chromatic number \( \chi(G) \) of a connected graph \( G \) are investigated and results and problems on \( \text{reg}(G) \) are presented.