Extremal problems in royal colorings of graphs

Abstract

An edge coloring $c$ of a graph $G$ is a royal $k$-edge coloring of $G$ if the edges of $G$ are assigned nonempty subsets of the set $\{1,2,\dots ,k\}$ in such a way that the vertex coloring obtained by assigning the union of the colors of the incident edges of each vertex is a proper vertex coloring. If the vertex coloring is vertex-distinguishing, then $c$ is a strong royal $k$-edge coloring. The minimum positive integer $k$ for which $G$ has a strong royal $k$-edge coloring is the strong royal index of $G$. It has been conjectured that if $G$ is a connected graph of order $n\ge 4$ where $2^{k-1}\le n\le 2^k–1$ for a positive integer $k$, then the strong royal index of $G$ is either $k$ or $k+1$. We discuss this conjecture along with other information concerning strong royal colorings of graphs. A sufficient condition for such a graph to have strong royal index $k+1$ is presented.