On Strong Regal and Strong Royal Colorings

Proof. First, we show that $\mathrm{sroy}(G)\le \mathrm{sreg}(G)+1$. Let $\mathrm{sreg}(G)=k$ and suppose that $c:E(G)\to {\mathcal{P}}^{\ast }([k])$ is a strong regal $k$-edge coloring of $G$ where the vertex coloring $c^{\prime }:V(G)\to {\mathcal{P}}^{\ast }([k])$ is a vertex-distinguishing vertex coloring induced by $c$. Define a complementary coloring $\overline{c}:E(G)\to {\mathcal{P}}^{\ast }([k+1])$ by $\overline{c}(e)=[k+1]-c(e)$. Then ${\overline{c}}^{\prime }:V(G)\to {\mathcal{P}}^{\ast }([k+1])$ is a strong royal $(k+1)$-edge coloring of $G$. Indeed, observe that $${\overline{c}}^{\prime }(v)=\bigcup _{e\in E_v}\overline{c}(e)=\bigcup _{e\in E_v}([k+1]-c(e))=[k+1]-c^{\prime }(v)$$ where $E_v$ is the set of edges incident to $v$. Note that ${\overline{c}}^{\prime }(v)$ is nonempty since $c^{\prime }(v)\subseteq [k]$. Since $c^{\prime }$ is vertex-distinguishing, it follows that ${\overline{c}}^{\prime }$ is also vertex-distinguishing. Hence, $\mathrm{sroy}(G)\le k+1=\mathrm{sreg}(G)+1$.

Next, we show that $\mathrm{sreg}(G)\le \mathrm{sroy}(G)+1$. Let $\mathrm{sroy}(G)=k$ and suppose that $c:E(G)\to {\mathcal{P}}^{\ast }([k])$ is a strong royal $k$-edge coloring of $G$ where the vertex coloring $c^{\prime }:V(G)\to {\mathcal{P}}^{\ast }([k])$ is a vertex-distinguishing vertex coloring induced by $c$. Define a complementary coloring $\overline{c}:E(G)\to {\mathcal{P}}^{\ast }([k+1])$ by $\overline{c}(e)=[k+1]-c(e)$. Then ${\overline{c}}^{\prime }:V(G)\to {\mathcal{P}}^{\ast }([k+1])$ is a strong regal $(k+1)$-edge coloring of $G$. Indeed, observe that $${\overline{c}}^{\prime }(v)=\bigcap _{e\in E_v}\overline{c}(e)=\bigcap _{e\in E_v}([k+1]-c(e))=[k+1]-c^{\prime }(v)$$ where $E_v$ is the set of edges incident to $v$. Note that ${\overline{c}}^{\prime }(v)$ is nonempty since $c^{\prime }(v)\subseteq [k]$. Since $c^{\prime }$ is vertex-distinguishing, it follows that ${\overline{c}}^{\prime }$ is also vertex-distinguishing. Hence, $\mathrm{sreg}(G)\le k+1=\mathrm{sroy}(G)+1$. Consequently, $\mathrm{sroy}(G)\ge \mathrm{sreg}(G)-1$ and so

Therefore, $$|\mathrm{sroy}(G)-\mathrm{sreg}(G)|\le 1.$$

Proof. Let $V(G)=\{v_1,v_2,\dots ,v_n\}$ and let $H=\mathrm{cor}(G)$ be obtained from $G$ by adding the pendant edge $u_i{v}_i$ at $v_i$ for $1\le i\le n$. Let $c_G:E(G)\to {\mathcal{P}}^{\ast }([k])$ be a strong regal $k$-edge coloring of $G$. Define an edge coloring $c_H:E(H)\to {\mathcal{P}}^{\ast }([k+1])$ by $$c_H(e)=\{\begin{array}{ll}{c}_G(e)& \text{ if }e\in E(G)\\ c_G^{\prime }(v_i)\cup \{k+1\}& \text{ if }e=u_i{v}_i\text{ for }1\le i\le n\text{.}\end{array}$$ Then the induced vertex coloring $c^{\prime }$ is given by

Since $c_H^{\prime }$ is vertex-distinguishing, it follows that $c_H$ is a strong regal $(k+1)$-edge coloring of $\mathrm{cor}(G)$ and so $\mathrm{sreg}(H)\le \mathrm{sreg}(G)+1$.

If $G$ is a connected graph of order $n\ge 4$ where $2^{k-1}\le n\le 2^k-1$, then $\mathrm{cor}(G)$ is a connected graph of order $2n\ge 8$ where $2^k\le 2n\le 2^{k+1}-2$. Since $\mathrm{sreg}(\mathrm{cor}(G))\ge k+1$ by Proposition 1 and there is a strong regal $(k+1)$-edge coloring of $\mathrm{cor}(G)$, it follows that $\mathrm{sreg}(\mathrm{cor}(G))=k+1$ and so $\mathrm{cor}(G)$ is regal-zero. 0
Though thus far we consider only connected graphs of order at least $3$, any graph whose connected components have order at least $3$ also have strong royal and strong regal colorings and, consequently, the associated chromatic parameters. Let $F$ and $H$ be two graphs with disjoint vertex sets. The union $G=F+H$ of $F$ and $H$ has vertex set $V(G)=V(F)\cup V(H)$ and edge set $E(G)=E(F)\cup E(H)$. The union $H+H$ of two disjoint copies of $H$ is denoted by $2H$. If a graph $G$ consists of $k$ ($\ge 2$) disjoint copies of a graph $H$, then we write $G=kH$.

Proof. Since the argument for both the royal and regal cases are similar, we prove the result for only the regal case. Suppose that $\mathrm{sreg}(F)=k_F$ and $\mathrm{sreg}(H)=k_H$, where say $k_F\le k_H$. Since the restriction of a strong regal coloring of $F+H$ to $H$ is also a strong regal coloring of $H$, it follows that

Thus, the lower bound holds. For the upper bound, we show that there is a strong regal $k_H$-edge coloring of $F+H$. Let $c_F$ be a strong regal $k_F$-edge coloring of $F$ and let $c_H$ be a strong regal $k_H$-edge coloring of $H$. Define an edge coloring $c:E(F+H)\to {\mathcal{P}}^{\ast }([k_H+1])$ by $$c(e)=\{\begin{array}{ll}{c}_F(e)& \text{ if }e\in E(F)\\ c_H(e)\cup \{k_H+1\}& \text{ if }e\in E(H)\text{.}\end{array}$$ Then the induced coloring $c^{\prime }:V(F+H)\to {\mathcal{P}}^{\ast }([k_H+1])$ is given by $$c^{\prime }(v)=\{\begin{array}{ll}{c}_F^{\prime }(v)& \text{ if }v\in V(F)\\ c_H^{\prime }(v)\cup \{k_H+1\}& \text{ if }v\in V(H)\text{.}\end{array}$$ Since $c_F^{\prime }$ and $c_H^{\prime }$ are vertex-distinguishing and $c^{\prime }(x)\ne c^{\prime }(y)$ if $x\in V(F)$ and $y\in V(H)$, it follows that $c^{\prime }$ is a vertex-distinguishing vertex coloring of $F+H$. Therefore, $c$ is a strong regal $k_H$-edge coloring of $F+H$. 0 Note that Proposition 4 cannot be improved. For example, we saw that $\mathrm{sreg}(P_3)=\mathrm{sreg}(K_3)=\mathrm{sreg}(P_3+K_3)=3$, but $\mathrm{sreg}(P_3)=\mathrm{sreg}(P_7)=3$ and $\mathrm{sreg}(P_3+P_7)=4$.

Let $F$ and $H$ be two graphs with disjoint vertex sets. The join $G=F\vee H$ of $F$ and $H$ has vertex set $V(G)=V(F)\cup V(H)$ and edge set

Proof. Let $G=F\vee H$. It suffices to show that a strong regal $s$-edge coloring and a strong royal $t$-edge coloring of $G$ exist for values of $s$ and $t$ corresponding to each desired upper bound.

First, we consider $\mathrm{sreg}(F\vee H)$. We may assume that

and so $max\{\mathrm{sreg}(F),\mathrm{sreg}(H)\}+1=k+1$. Then there are strong regal $k$-edge colorings $c_F:E(F)\to {\mathcal{P}}^{\ast }([k])$ and $c_H:E(H)\to {\mathcal{P}}^{\ast }([k])$ of $F$ and $H$ with vertex-distinguishing induced vertex colorings $c_F^{\prime }$ and $c_H^{\prime }$ respectively. Define an edge coloring $c:E(G)\to {\mathcal{P}}^{\ast }([k+1])$ by

$$c(e)=\{\begin{array}{ll}{c}_F(e)& \text{ if }e\in E(F)\\ c_H(e)\cup \{k+1\}& \text{ if }e\in E(H)\\ \{k+1\}& \text{ otherwise.}\end{array}$$ Then the induced coloring $c^{\prime }:V(G)\to {\mathcal{P}}^{\ast }([k+1])$ is given by $$c^{\prime }(v)=\{\begin{array}{ll}{c}_F^{\prime }(v)& \text{ if }v\in V(F)\\ c_H^{\prime }(v)\cup \{k+1\}& \text{ if }v\in V(H)\text{.}\end{array}$$ Since $c_F^{\prime }$ and $c_H^{\prime }$ are vertex-distinguishing and $c^{\prime }(x)\ne c^{\prime }(y)$ if $x\in V(F)$ and $y\in V(H)$, it follows that $c^{\prime }$ is a vertex-distinguishing vertex coloring of $G$. Therefore, $c$ is a strong regal $(k+1)$-edge coloring of $G=F\vee H$.

Next, we consider $\mathrm{sroy}(F\vee H)$. We may assume that

and so $max\{\mathrm{sroy}(F),\mathrm{sroy}(H)\}+2=k+2$. Then there are strong royal $k$-edge colorings $c_F:E(F)\to {\mathcal{P}}^{\ast }([k])$ and $c_H:E(H)\to {\mathcal{P}}^{\ast }([k])$ of $F$ and $H$ with vertex-distinguishing induced vertex colorings $c_F^{\prime }$ and $c_H^{\prime }$ respectively. Define an edge coloring $c:E(G)\to {\mathcal{P}}^{\ast }([k+2])$ by

$$c(e)=\{\begin{array}{ll}{c}_F(e)& \text{ if }e\in E(F)\\ c_H(e)\cup \{k+1\}& \text{ if }e\in E(H)\\ \{k+2\}& \text{ otherwise.}\end{array}$$ Then the induced coloring $c^{\prime }:V(G)\to {\mathcal{P}}^{\ast }([k+2])$ is given by $$c^{\prime }(v)=\{\begin{array}{ll}{c}_F^{\prime }(v)\cup \{k+2\}& \text{ if }v\in V(F)\\ c_H^{\prime }(v)\cup \{k+1,k+2\}& \text{ if }v\in V(H)\text{.}\end{array}$$

Since $c_F^{\prime }$ and $c_H^{\prime }$ are vertex-distinguishing and $c^{\prime }(x)\ne c^{\prime }(y)$ if $x\in V(F)$ and $y\in V(H)$, it follows that $c^{\prime }$ is a vertex-distinguishing vertex coloring of $G$. Therefore, $c$ is a strong royal $(k+2)$-edge coloring of $G=F\vee H$. 0
Equality can be obtained for both bounds. Note that $\mathrm{sreg}(P_3)=3$ and $\mathrm{sroy}(P_3\vee P_3)=4$ while $\mathrm{sroy}(P_3)=2$ and $\mathrm{sroy}(P_3\vee P_3)=4$.

Let $F$ and $H$ be two graphs with disjoint vertex sets. The Cartesian product $G=F\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}H$ of $F$ and $H$ has vertex set $V(G)=V(F)\times V(H)$, where two distinct vertices $(u,v)$ and $(x,y)$ of $F\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}H$ are adjacent if either $u=x$ and $vy\in E(H)$ or $v=y$ and $ux\in E(F)$. In particular, the graph $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2$ consists of two copies $G_1$ and $G_2$ of $G$. If $V(G_1)=\{u_1,u_2,\dots u_n\}$ where $u_i$ is labeled $v_i$ in $G_2$, then $V(G_2)=\{v_1,v_2,\dots ,v_n\}$ and

If $G$ is a connected graph of order $n\ge 4$ where $2^{k-1}\le n\le 2^k-1$ for some integer $k$, then $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2$ is a connected graph of order $2n\ge 8$ where $2^k\le 2n\le 2^{k+1}-2$. Therefore, $\mathrm{sreg}(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2)\ge k+1$ by Proposition 1. A bound was given for $\mathrm{sroy}(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2)$ in terms of $\mathrm{sroy}(G)$ in [4].

Proof. Suppose that $\mathrm{sreg}(G)=k$. Then it suffices to show that there exists a strong regal $(k+1)$-edge coloring of $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2$. By definition, $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2$ consists of two copies of $G$, say $G_1$ and $G_2$ as describe previously. There exist strong regal $k$-edge colorings $c_1:E(G_1)\to {\mathcal{P}}^{\ast }([k])$ and $c_2:E(G_2)\to {\mathcal{P}}^{\ast }([k])$ with vertex-distinguishing induced vertex colorings $c_1^{\prime }$ and $c_2^{\prime }$ respectively.

Define an edge coloring $c:E(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2)\to {\mathcal{P}}^{\ast }([k+1])$ by

$$c(e)=\{\begin{array}{ll}{c}_1(e)& \text{ if }e\in E(G_1)\\ c_2(e)\cup \{k+1\}& \text{ if }e\in E(G_2)\\ \{k+1\}& \text{ otherwise.}\end{array}$$ Then the induced coloring $c^{\prime }:V(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2)\to {\mathcal{P}}^{\ast }([k+1])$ is given by $$c^{\prime }(v)=\{\begin{array}{ll}{c}_1^{\prime }(v)& \text{ if }v\in V(G_1)\\ c_2^{\prime }(v)\cup \{k+1\}& \text{ if }v\in V(G_2)\text{.}\end{array}$$ Since $c_1^{\prime }$ and $c_2^{\prime }$ are vertex-distinguishing and $c^{\prime }(x)\ne c^{\prime }(y)$ if $x\in V(G_1)$ and $y\in V(G_2)$, it follows that $c^{\prime }$ is a vertex-distinguishing vertex coloring of $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2$. Therefore, $c$ is a strong regal $(k+1)$-edge coloring of $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{K}_2$. 0

Proof. Let $k=1+\lfloor {\log }_{2}n\rfloor$, where $n\ge 4$ and $n\ne 7$. Figure 1 shows that $P_n$ has such a coloring for $n\in [4,6]\cup [12,15]$. Notice in each case that if $[k]$ is an induced color, it is induced on an end vertex. Observe that the induced vertex coloring of each path $P_n$ in Figure 1 for $n\in [4,5]\cup [12,15]$ contains two adjacent vertices whose colors are disjoint. For an integer $n\in [4,5]\cup [12,15]$, let

be the path $P_n$ of order $n$ and let

be the path $P_n$ in reverse order. Let $c_H$ be the edge coloring of $H$ shown in Figure 1. Notice that for the colorings of $P_4$ and $P_{13}$ of Figure 1, since $[k]$ (where $k=3$ for $P_4$ and $k=4$ for $P_{13}$) is not the induced vertex color of any vertex in each of these two colorings, it follows that both colorings satisfy the conditions in the statement vacuously.

We now define a strong regal $(k+1)$-coloring $c_{H^{\star }}:E(H^{\star })\to {\mathcal{P}}^{\ast }([k+1])$ of $H^{\star }$ by

Let $G$ be the path of order $2n$ obtained from $H$ and $H^{\star }$ by joining the two vertices $v_n$ in $H$ and $H^{\star }$ by the edge $f$. The edge coloring $c_G:E(G)\to {\mathcal{P}}^{\ast }([k+1])$ is defined by $$c_G(e)=\{\begin{array}{ll}{c}_H(e)& \text{ if }e\in E(H)\\ c_{H^{\star }}(e)& \text{ if }e\in E(H^{\star })\\ c_{H^{\star }}(v_n{v}_{n-1})& \text{ if }e=f.\end{array}$$ The coloring $c_G$ is illustrated in Figure 2 for $G=P_{10}$ when $n=5$. Note that, in order for $[k+1]$ to be an induced color of a vertex in $G$, $[k]$ had to be an induced color of a vertex in $H$. By Figure 1, if such a vertex exists, it must be $v_1$, in which case $c_{H^{\star }}(v_1)=[k+1]$, which implies that $[k+1]$ is assigned to an end vertex of $G$. Since this edge coloring is a strong regal $(k+1)$-coloring of the path $G$ of order $2n$, it follows that the desired result holds for order $n=2\ell$, with $\ell \ge 2$.

Next, for each $n\in [4,5]\cup [12,15]$, let $F$ be the path of $n+1$ obtained from $H$ by subdividing an edge $v_j{v}_{j+1}$ of $H$ where $c_H^{\prime }(v_j)\cap c_H^{\prime }(v_{j+1})=\mathrm{\varnothing }$, obtaining the subpath $(v_j,u,v_{j+1})$. Define an edge coloring $c_F$ of $F$ by $$c_F(e)=\{\begin{array}{ll}{c}_H^{\prime }(v_j)& \text{ if }e=v_{j}u\\ c_H^{\prime }(v_{j+1})& \text{ if }e=u{v}_{j+1}\\ c_H(e)& \text{ if }e\ne v_{j}u,u{v}_{j+1}\text{.}\end{array}$$ (The edge coloring $c_F$ is not a regal edge coloring since $c_F^{\prime }(u)=\mathrm{\varnothing }$.) Let

be the path $F$ in reverse order. Define the edge coloring $c_{F^{\star }}:E(F^{\star })\to {\mathcal{P}}^{\ast }([k+1])$ of $F^{\star }$ by

Then $c_{F^{\star }}^{\prime }(v_i)=c_H^{\prime }(v_i)\cup \{k+1\}$ for $1\le i\le n$ and $c_{F^{\star }}^{\prime }(u)=\{k+1\}$. In particular, $c_{F^{\star }}^{\prime }(v_1)=[k+1]$. Since $c_{F^{\star }}^{\prime }$ is vertex-distinguishing, it follows that $c_{F^{\star }}$ is a strong regal $(k+1)$-coloring of $F^{\star }$. The graphs $H$, $F$ and $F^{\star }$ are shown in Figure 3 as well as the corresponding edge colorings.

Let $G$ be the path of order $2n+1$ obtained from $H$ and $F^{\star }$ by joining the vertex $v_n$ in $H$ and $F^{\star }$ by the edge $f$. The edge coloring $c_G:E(G)\to {\mathcal{P}}^{\ast }([k+1])$ is defined by $$c_G(e)=\{\begin{array}{ll}{c}_H(e)& \text{ if }e\in E(H)\\ c_{F^{\star }}(e)& \text{ if }e\in E(F^{\star })\\ c_{F^{\star }}(v_n{v}_{n-1})& \text{ if }e=f.\end{array}$$ The coloring $c_G$ is illustrated in Figure 3 for $G=P_{11}$ when $n=5$. This edge coloring is a strong regal $(k+1)$-coloring of the path $G$ of order $2n+1$, where if $[k+1]$ appears as an induced color, it is induced on an end vertex.

The colorings defined above show, in particular, that if $n\in [4,31]$ where $n\ne 7$, then $P_n$ has a strong regal $k$– coloring with $k=1+\lfloor {\log }_{2}n\rfloor$ such that if $[k]$ appears as an induced color, it is induced on an end vertex. Furthermore, the induced vertex coloring of each such path $P_n$ where $n\in [16,31]$ has the property that there exist two adjacent vertices whose colors are disjoint and $[5]$ is induced on an end vertex if it appears in the induced coloring. By proceeding as above, we see that if $n\in [32,63]$, then there is a strong regal $1+\lfloor {\log }_{2}n\rfloor$ coloring of $P_n$ such that the induced vertex coloring of each such path has the property that there exist two adjacent vertices whose colors are disjoint and $[6]$ is induced on an end vertex if it appears in the induced coloring. Consequently, for each integer $\ell \ge 2$ and each integer $n\in [2^{\ell },2^{\ell +1}-1]$ except $n=7$ the result holds. That is, for each integer $n\ge 4$ and $n\ne 7$, there exist a strong regal $k$-coloring of $P_n$, say $c$, with such that if $c^{\prime }(u)=[k]$ for some vertex $u\in V(P_n)$, then $u$ is a leaf of $P_n$ . 0

Proof. By Proposition 1, it suffices to show that a strong regal $k$-coloring exists, where $k=1+\lfloor {\log }_{2}n\rfloor$. If $n=4$, then $T$ is a star and the result holds. Since every vertex in a cubic caterpillar has odd degree, $n$ must be even. Assume $n=2\ell$ where $\ell \ge 3$ . Let $P_s=(v_1,v_2,v_3,\dots ,v_s)$ be the shortest path in $T$ such that every vertex in $T$ has distance at most one from a vertex in $P_s$. This implies that $v_1$ and $v_s$ are each adjacent to at least one other vertex not in $P_s$, say $v_0$ and $v_{s+1}$ respectively, for otherwise $P_s$ would not be a minimum path with the designated property. Since each vertex $v\in V(P_s)$ has ${\mathrm{deg}}_T(v)\ge 2$, each vertex in $P_s$ must have exactly $3$ neighbors, so each vertex $v_i$ in $P_s$ is adjacent to another vertex $u_i$ not in $P_s$, for $1\le i\le s$. Note that since $T$ is a caterpillar, $\mathrm{deg}(u_i)=1$ for $1\le i\le s$. This implies the order of $T$ is $2s+2$. Let $P=(v_0,v_1,v_2,\dots ,v_s)$. Since the order of $T$ is even, $2^{k-1}\le n\le 2^k-2$. If follows that $2^{k-2}\le \frac{n}{2}\le 2^{k-1}-1$. Observe that the order of $P$ is $s+1=\frac{n}{2}$. Then, by Lemma 1 it follows that $P$ has a strong regal $k-1$-coloring, say $c_P$, and we may assume that