Color-induced graph colorings

Abstract

For a positive integer $k$, let $P^{\ast }([k])$ denote the set of nonempty subsets of $[k]=\{1,2,\dots ,k\}$. For a graph $G$ without isolated vertices, let $c:E(G)\to 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 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 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 a graph $G$ has a strong regal $k$-edge coloring is the strong regal index of $G$. The regal index (and, consequently, the strong regal index) is determined for each complete graph and for each complete multipartite graph. Sharp bounds for regal indexes and strong regal indexes of connected graphs are established. Strong regal indexes are also determined for several classes of trees. Other results and problems are also presented.