On Regal Colorings of Graphs

Abstract

For a positive integer $k$, let ${\mathcal{P}}^{\ast }([k])$ be the set of nonempty subsets of the set $[k]=\{1,2,\dots ,k\}$. For a connected graph $G$ of order 3 or more, let $c:E(G)\to {\mathcal{P}}^{\ast }([k])$ be an edge coloring of $G$ where adjacent edges may be colored the same. The induced vertex coloring $c^{\prime }:V(G)\to {\mathcal{P}}^{\ast }([k])$ is defined by $c^{\prime }(v)=\bigcap _{e\in E_v}c(e)$, where $E_v$ is the set of edges incident with $v$. If $c^{\prime }$ 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^{\prime }$ 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.