On Strong Regal and Strong Royal Colorings

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

Next, we show that \(\mathop{\rm sreg}(G)\leq \mathop{\rm sroy}(G)+1\). Let \(\mathop{\rm sroy}(G)=k\) and suppose that \(c:E(G)\to {\cal P}^*([k])\) is a strong royal \(k\)-edge coloring of \(G\) where the vertex coloring \(c':V(G)\to {\cal P}^*([k])\) is a vertex-distinguishing vertex coloring induced by \(c\). Define a complementary coloring \(\overline{c}:E(G)\to {\cal P}^*([k+1])\) by \(\overline{c}(e)=[k+1]-c(e)\). Then \(\overline{c}':V(G)\to {\cal P}^*([k+1])\) is a strong regal \((k+1)\)-edge coloring of \(G\). Indeed, observe that \[\overline{c}'(v)=\bigcap_{e\in E_v}\overline{c}(e)=\bigcap_{e\in E_v}\left([k+1]-c(e)\right)=[k+1]-c'(v)\] where \(E_v\) is the set of edges incident to \(v\). Note that \(\overline{c}'(v)\) is nonempty since \(c'(v)\subseteq [k]\). Since \(c'\) is vertex-distinguishing, it follows that \(\overline{c}'\) is also vertex-distinguishing. Hence, \(\mathop{\rm sreg}(G)\leq k+1=\mathop{\rm sroy}(G)+1\). Consequently, \(\mathop{\rm sroy}(G)\geq \mathop{\rm sreg}(G)-1\) and so

Therefore, \[|\mathop{\rm sroy}(G)-\mathop{\rm sreg}(G)|\leq 1.\] ◻

Proof. Let \(V(G)=\{v_1, v_2, \ldots, v_n\}\) and let \(H = \mathop{\rm cor}(G)\) be obtained from \(G\) by adding the pendant edge \(u_iv_i\) at \(v_i\) for \(1 \le i \le n\). Let \(c_G: E(G) \to {\cal P}^*([k])\) be a strong regal \(k\)-edge coloring of \(G\). Define an edge coloring \(c_H: E(H) \to {\cal P}^*([k+1])\) by \[c_H(e)=\left\{ \begin{array}{ll} c_G(e) & \mbox{ if $e \in E(G)$}\\ c'_G(v_i) \cup \{k+1\} & \mbox{ if $e= u_iv_i$ for $1 \le i \le n$.} \end{array}\right.\] Then the induced vertex coloring \(c'\) is given by

Since \(c'_H\) is vertex-distinguishing, it follows that \(c_H\) is a strong regal \((k+1)\)-edge coloring of \(\mathop{\rm cor}(G)\) and so \(\mathop{\rm sreg}(H) \le \mathop{\rm 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 \(\mathop{\rm cor}(G)\) is a connected graph of order \(2n \ge 8\) where \(2^{k} \le 2n \le 2^{k+1}-2\). Since \(\mathop{\rm sreg}(\mathop{\rm cor}(G)) \ge k+1\) by Proposition 1 and there is a strong regal \((k+1)\)-edge coloring of \(\mathop{\rm cor}(G)\), it follows that \(\mathop{\rm sreg}(\mathop{\rm cor}(G))= k+1\) and so \(\mathop{\rm 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 \(\mathop{\rm sreg}(F) = k_F\) and \(\mathop{\rm 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 {\cal P}^*([k_H+1])\) by \[c(e) =\left\{ \begin{array}{ll} c_F(e) & \mbox{ if $e\in E(F)$}\\ c_H(e)\cup \{k_H+1\} & \mbox{ if $e\in E(H)$.} \end{array} \right.\] Then the induced coloring \(c': V(F + H ) \to {\cal P}^*([k_H+1])\) is given by \[c'(v) =\left\{ \begin{array}{ll} c'_F(v) & \mbox{ if $v\in V(F)$}\\ c'_H(v)\cup \{k_H+1\} & \mbox{ if $v\in V(H)$.} \end{array} \right.\] Since \(c'_F\) and \(c'_H\) are vertex-distinguishing and \(c'(x) \ne c'(y)\) if \(x \in V(F)\) and \(y \in V(H)\), it follows that \(c'\) 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 \(\mathop{\rm sreg}(P_3)=\mathop{\rm sreg}(K_3) = \mathop{\rm sreg}(P_3+K_3) =3\), but \(\mathop{\rm sreg}(P_3) =\mathop{\rm sreg}(P_7) = 3\) and \(\mathop{\rm 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 \(\mathop{\rm sreg}(F\vee H)\). We may assume that

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

\[c(e) =\left\{ \begin{array}{ll} c_F(e) & \mbox{ if $e\in E(F)$}\\ c_H(e)\cup \{k+1\} & \mbox{ if $e\in E(H)$}\\ \{k+1\} & \mbox{ otherwise.} \end{array} \right.\] Then the induced coloring \(c': V(G ) \to {\cal P}^*([k+1])\) is given by \[c'(v) =\left\{ \begin{array}{ll} c'_F(v) & \mbox{ if $v\in V(F)$}\\ c'_H(v)\cup \{k+1\} & \mbox{ if $v\in V(H)$.} \end{array} \right.\] Since \(c'_F\) and \(c'_H\) are vertex-distinguishing and \(c'(x) \ne c'(y)\) if \(x \in V(F)\) and \(y \in V(H)\), it follows that \(c'\) 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 \(\mathop{\rm sroy}(F \vee H)\). We may assume that

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

\[c(e) =\left\{ \begin{array}{ll} c_F(e) & \mbox{ if $e\in E(F)$}\\ c_H(e)\cup \{k+1\} & \mbox{ if $e\in E(H)$}\\ \{k+2\} & \mbox{ otherwise.} \end{array} \right.\] Then the induced coloring \(c': V(G) \to {\cal P}^*([k+2])\) is given by \[c'(v) =\left\{ \begin{array}{ll} c'_F(v)\cup \{k+2\} & \mbox{ if $v\in V(F)$}\\ c'_H(v)\cup \{k+1,k+2\} & \mbox{ if $v\in V(H)$.} \end{array} \right.\]

Since \(c'_F\) and \(c'_H\) are vertex-distinguishing and \(c'(x) \ne c'(y)\) if \(x \in V(F)\) and \(y \in V(H)\), it follows that \(c'\) 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 \(\mathop{\rm sreg}(P_3)=3\) and \(\mathop{\rm sroy}(P_3\vee P_3)=4\) while \(\mathop{\rm sroy}(P_3)=2\) and \(\mathop{\rm sroy}(P_3\vee P_3)=4\).

Let \(F\) and \(H\) be two graphs with disjoint vertex sets. The Cartesian product \(G = F \ \Box \ 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 \ \Box \ 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\ \Box \ 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\ \Box \ K_2\) is a connected graph of order \(2n \ge 8\) where \(2^{k} \le 2n \le 2^{k+1}-2\). Therefore, \(\mathop{\rm sreg}(G\ \Box \ K_2) \ge k+1\) by Proposition 1. A bound was given for \(\mathop{\rm sroy}(G\ \Box \ K_2)\) in terms of \(\mathop{\rm sroy}(G)\) in [4]. ◻

Proof. Suppose that \(\mathop{\rm sreg}(G)=k\). Then it suffices to show that there exists a strong regal \((k+1)\)-edge coloring of \(G\ \Box \ K_2\). By definition, \(G\ \Box \ 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 {\cal P}^*([k])\) and \(c_2:E(G_2) \to {\cal P}^*([k])\) with vertex-distinguishing induced vertex colorings \(c_1'\) and \(c_2'\) respectively.

Define an edge coloring \(c: E(G\ \Box \ K_2) \to {\cal P}^*([k+1])\) by

\[c(e) =\left\{ \begin{array}{ll} c_1(e) & \mbox{ if $e\in E(G_1)$}\\ c_2(e)\cup \{k+1\} & \mbox{ if $e\in E(G_2)$}\\ \{k+1\} & \mbox{ otherwise.} \end{array} \right.\] Then the induced coloring \(c': V(G\ \Box \ K_2) \to {\cal P}^*([k+1])\) is given by \[c'(v) =\left\{ \begin{array}{ll} c'_1(v) & \mbox{ if $v\in V(G_1)$}\\ c'_2(v)\cup \{k+1\} & \mbox{ if $v\in V(G_2)$.} \end{array} \right.\] Since \(c'_1\) and \(c'_2\) are vertex-distinguishing and \(c'(x) \ne c'(y)\) if \(x \in V(G_1)\) and \(y \in V(G_2)\), it follows that \(c'\) is a vertex-distinguishing vertex coloring of \(G\ \Box \ K_2\). Therefore, \(c\) is a strong regal \((k+1)\)-edge coloring of \(G\ \Box \ 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 {\cal P}^*([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 {\cal P}^*([k+1])\) is defined by \[c_G(e)=\left\{ \begin{array}{ll} c_H(e) & \mbox{ if $e \in E(H)$}\\ c_{H^{\star}}(e) & \mbox{ if $e \in E(H^{\star})$}\\ c_{H^{\star}}(v_nv_{n-1}) & \mbox{ if $e = f.$} \end{array}\right.\] 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_jv_{j+1}\) of \(H\) where \(c'_H(v_j) \cap c'_H(v_{j+1}) = \emptyset\), obtaining the subpath \((v_j, u, v_{j+1})\). Define an edge coloring \(c_F\) of \(F\) by \[c_F(e)=\left\{ \begin{array}{ll} c'_H(v_j) & \mbox{ if $e= v_ju$}\\ c'_H(v_{j+1}) & \mbox{ if $e= uv_{j+1}$}\\ c_{H}(e) & \mbox{ if $e \ne v_ju, uv_{j+1}$.} \end{array}\right.\] (The edge coloring \(c_F\) is not a regal edge coloring since \(c'_F(u)= \emptyset\).) Let

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

Then \(c'_{F^{\star}}(v_i) = c'_H(v_i) \cup \{k+1\}\) for \(1 \le i \le n\) and \(c'_{F^{\star}}(u) =\{k+1\}\). In particular, \(c'_{F^{\star}}(v_1)=[k+1]\). Since \(c'_{F^{\star}}\) 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 {\cal P}^*([k+1])\) is defined by \[c_G(e)=\left\{ \begin{array}{ll} c_H(e) & \mbox{ if $e \in E(H)$}\\ c_{F^{\star}}(e) & \mbox{ if $e \in E(F^{\star})$}\\ c_{F^{\star}}(v_nv_{n-1}) & \mbox{ if $e = f.$} \end{array}\right.\] 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'(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\geq 3\) . Let \(P_s=(v_1,v_2,v_3,\ldots, 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 \(\deg_T(v)\geq 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\leq i\leq s\). Note that since \(T\) is a caterpillar, \(\deg(u_i)=1\) for \(1\leq i\leq 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}\leq n\leq 2^k-2\). If follows that \(2^{k-2}\leq \frac{n}{2}\leq 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

Define a coloring \(c:E(T)\to{\cal P}^*([k])\) by \[c(e)=\left\{ \begin{array}{ll} c_P(e) & \mbox{ if $e \in E(P)$}\\ c'_P(v_i)\cup \{k\} & \mbox{ if $e=u_iv_i$, $1\le i\le s$}\\ $[k]$ & \mbox{ if \(e = v_s v_{s+1}\).} \end{array}\right.\] Then, the induced coloring \(c':V(T)\to{\cal P}^*([k])\) is given by \[c'(v)=\left\{ \begin{array}{ll} c'_P(v) & \mbox{ if $v \in V(P)$}\\ c'_P(v_i)\cup \{k\} & \mbox{ if $v=u_i$, $1\le i\le s$}\\ $[k]$ & \mbox{ if $v = v_{s+1}$.} \end{array}\right.\] It follows that \(c'\) is neighbor distinguishing since no neighbor of a vertex \(u_i\) is assigned the color \(\{1,2,\dots,k-1\}\) by \(c_P'\). Thus, \(c\) is a strong regal \(k\) coloring of \(T\) and so \(\mathop{\rm sreg}(T)=1 + \lfloor{\log_2 n}\rfloor\). ◻

Proof. Consider a royal coloring \(c\) of \(G\). Since the induced vertex coloring \(c'\) must be proper, it must use at least \(\chi(G)\) colors, however no vertex coloring can use more colors than the number of vertices in the graph. Consequently, \(\chi(G)\leq\chi_{\mathop{\rm roy}}(G)\leq n\). Next, we obtain that \(\chi_{\mathop{\rm roy}}(G)\geq 3\). Since \(G\) is nonempty, \(\chi(G)\geq 2\), so \(\chi_{\mathop{\rm roy}}(G)\geq 2\). It suffices to show that \(\chi_{\mathop{\rm roy}}(G)\not= 2\). Assume, to the contrary, that \(\chi_{\mathop{\rm roy}}(G)=2\). Then, there exists a royal \(k\)-edge coloring \(c\) of \(G\) such that the induced vertex coloring \(c'\) uses exactly two distinct vertex colors, say sets \(A\) and \(B\). Let \(u\) be a vertex in \(G\) such that \(c'(u)=A\). Then, for any vertex \(w\in N(u)\), \(c'(w)=B\), since \(c'\) is proper. It follows that \(c(e)\subseteq B\) for every edge incident to \(u\), since \(e\) is incident to a neighbor of \(u\). This implies that \(A\subseteq B\). Considering a symmetric argument, \(B\subseteq A\), which demonstrates that \(A=B\), which is impossible because of our assumption that \(A\) and \(B\) were distinct colors. Next, a royal \(k\)-edge coloring of \(G\) can use at most \(2^k-1\) vertex colors, given \(|{\cal P}^*([k])|=2^k-1\), which implies that \(\chi_{\mathop{\rm roy}}\mathop{\rm roy}(G)\leq 2^k-1\) for any graph \(G\) with \(\mathop{\rm roy}(G)=k\). It follows that \(\displaystyle\mathop{\rm roy}(G)\geq \lceil\log_2(\chi_{\mathop{\rm roy}}(G)+1)\rceil\). Lastly, suppose that \(\mathop{\rm maj}(G)=\mathop{\rm roy}(G)=k\) and let \(\chi_{\mathop{\rm maj}}(G)=\ell\). Then, there exists a majestic \(k\)-edge coloring of \(G\) that uses exactly \(\ell\) distinct vertex colors. However, every majestic coloring is also a royal coloring. Thus, \(\chi_{\mathop{\rm roy}}(G)\leq \ell\). 0◻ Note that \(\chi_{\mathop{\rm roy}}(K_n)=n\), which demonstrates that the upper bound on the royal chromatic number given in Proposition 10 is sharp. Recall an observation involving the majestic chromatic number. ◻

Proof. First note that in [6], it is shown that \(\mathop{\rm maj}(P_4)=3\). Also, \(\mathop{\rm roy}(G)\leq \mathop{\rm maj}(G)\). By Proposition 5, it follows that \(\mathop{\rm roy}(P_4)=3\). Since \(\chi_{\mathop{\rm roy}}(P_4)\geq 3\) and \(\mathop{\rm roy}(P_4)=3\), we must show no royal \(3\)-edge coloring exists that uses only \(3\) induced vertex colors. Assume, to the contrary, that there is a royal \(3\)-edge coloring \(c:E(P_4)\to {\cal P}^*([3])\) such that the induced vertex coloring \(c':V(P_4)\to {\cal P}^*([3])\) uses only \(3\) colors. Let \(P_4=(u_1,u_2,u_3,u_4)\). In order to properly color \(P_4\) using less than \(4\) colors, two vertices must be assigned the same color by \(c'\). If \(c'(u_1)=c'(u_4)=A\), then \(c(u_1u_2)=A\) and \(c(u_3u_4)=A\). Thus, for any set \(c(u_2u_3)\), \(c'(u_2)=c'(u_3)\), a contradiction. We may assume \(c'(u_1)=c'(u_3)=A\), with \(A\subseteq[3]\). Since \(c'\) is proper, we must have that \(c'(u_2)=B\), with \(B\subseteq[3]\) and \(A\not=B\). It follows that \(c(u_1u_2)=A\), \(c(u_1u_2)\subseteq B\) and \(c(u_2u_3)\subseteq A\), so \(c'(u_2)=B\subseteq A\) and \(c'(u_1)=A\subseteq B\). However, this implies that \(A=B\), which is impossible, since \(c'\) is proper. Define a royal \(3\)-edge coloring \(c\) of \(P_4\) by the sequence \(s=(\{1\},\{2\},\{3\})\). Then, the induced vertex coloring \(c'\) is given by the color sequence \(s'=(\{1\},\{1,2\},\{2,3\},\{3\})\), which is a proper vertex coloring of \(C_5\) using exactly 4 colors. 0◻ ◻

Proof. By Proposition 10, \(\chi_{\mathop{\rm roy}}(P_n)\geq 3\). It suffices to show that a royal \(k\)-edge coloring of \(P_n\) exists using exactly \(3\) vertex colors, where \(k=\mathop{\rm roy}(P_n)\). We consider two cases Case \(1\). \(n\) is odd. If \(n\) is odd, then \(\mathop{\rm roy}(P_n)=2\), since \(\mathop{\rm maj}(P_n)=2\) when \(n\) is odd (see [6]. The desired result follows from Proposition 11. Case \(2\). \(n\) is even. Since \(\mathop{\rm maj}(P_n)=3\) for even \(n\) (see [6], it follows that \(\mathop{\rm roy}(P_n)=3\) by Proposition 11. Let \(P_n=(u_1,u_2,\dots, u_n)\). Define a royal \(3\)-edge coloring \(c:E(G)\to {\cal P}^*([3])\) of \(P_n\) by \[c(u_iu_{i+1}) = \left\{ \begin{array}{ll} 1 & \mbox{ if $i=3$}\\ 2 & \mbox{ if $i=4$}\\ 3 & \mbox{ if $i= 2$}\\ \{1,2\} & \mbox{ if $i=1$ or $i\equiv 0,3\ (\mathrm{mod}\ {4}$ for $7\leq i\leq n-1$}\\ \{1,3\} & \mbox{ if $i\equiv 1,2\ (\mathrm{mod}\ {4}$ for $5\leq i\leq n-1$.} \end{array}\right.\] Then, the induced coloring \(c':V(P_n)\to {\cal P}^*([3])\) is given by \[c'(u_i) = \left\{ \begin{array}{ll} \{1,2\} & \mbox{ if $i=1$ or $i\equiv 0\ (\mathrm{mod}\ {4}$ for $4\leq i\leq n$}\\ \{1,3\} & \mbox{ if $i=3$ or $i\equiv 2\ (\mathrm{mod}\ {4}$ for $6\leq i\leq n$}\\ \{3\}& \mbox{ if $i=2$ or $i\equiv 1,3\ (\mathrm{mod}\ {4}$ for $5\leq i\leq n-1$.} \end{array}\right.\] Since \(c'\) is a proper \(3\)-coloring of \(G\), it follows that \(\chi_{\mathop{\rm roy}}(P_n)=3\) for \(n\geq 3\), with \(n\not=4\). 0◻ For a cycle \(C_n\) of order \(n\geq 3\), \(\chi_{\mathop{\rm maj}}(C_n)=3\) if and only if \(n\equiv 0 \ (\mathrm{mod}\ {4}\) or \(n\equiv 0\ \ (\mathrm{mod}\ {3}\) by results in [6]. Otherwise \(\chi_{\mathop{\rm maj}}(C_n)\geq 4\). As with paths, the royal chromatic number of cycles contrasts that of the majestic chromatic number by achieving the lower bound given in Proposition 11 in all but one case. ◻

Proof. First, \(\mathop{\rm maj}(C_5)=3\) (see [6]. By Proposition 11, it follows that \(\mathop{\rm roy}(C_5)=3\). Since \(\chi_{\mathop{\rm roy}}(C_5)\geq 3\) and \(\mathop{\rm roy}(C_5)=3\), we must show no royal \(3\)-edge coloring exists that uses only \(3\) induced vertex colors and exhibit a royal \(3\)-edge coloring that uses exactly \(4\) induced vertex colors. First, assume to the contrary that a royal \(3\)-edge coloring \(c:E(C_5)\to {\cal P}^*([3])\) exists such that the induced vertex coloring \(c':V(C_5)\to {\cal P}^*([3])\) uses only \(3\) colors. Let \(C_5=(u_0,u_1,u_2,u_3,u_4,u_5=u_0)\). Observe that a proper coloring of \(C_5\) may assign the same color to at most two vertices in \(C_5\). It follows that two pairs of vertices in \(C_5\) must be assigned the same color by \(c'\). We may assume that \(c'(u_0)=c'(u_2)=A\), for some \(A\subseteq [3]\). Since \(c'\) is proper \(c'(u_3)\not=c'(u_4)\), so either \(c'(u_1)=c'(u_3)\) or \(c'(u_1)=c'(u_4)\). Without loss of generality, let \(c'(u_1)=c'(u_3)=B\), with \(B\subseteq [3]\). Then, \(A\not=B\). However, since \(u_0u_1\) and \(u_1u_2\) are both incident to a vertex colored \(A\), \(c(u_0u_1)\subseteq A\) and \(c(u_1u_2)\subseteq A\). These are the only edges incident to \(u_1\), hence \(c'(u_1)=B\subseteq A\). Similarly, since \(u_1u_2\) and \(u_2u_3\) are both incident to a vertex colored \(B\), \(c(u_1u_2)\subseteq B\) and \(c(u_2u_3)\subseteq B\). These are the only edges incident to \(u_2\), hence \(c'(u_2)=A\subseteq B\). This implies that \(A=B\), which is impossible since \(c'\) must be proper.

Now, define a royal \(3\)-edge coloring \(c\) of \(C_5\) by the sequence \[s=(\{1\},\{1\},\{1,2\},\{3\},\{2\}).\] Then, the induced vertex coloring \(c'\) is given by the color sequence \[s'=(\{1,2\},\{1\},\{1,2\},[3],\{2,3\}),\] which is a proper vertex coloring of \(C_5\) using exactly 4 colors. ◻

Proof. By Proposition 10, \(\chi_{\mathop{\rm roy}}(C_n)\geq 3\). It suffices to show that there exists a royal \(k\)-edge coloring \(C_n\) using exactly \(3\) vertex colors, where \(k=\mathop{\rm roy}(C_n)\). Let \(C_n=(u_0,u_2,\dots, u_n=u_0)\). We consider four cases. Case \(1\). \(n\equiv 0 \ (\mathrm{mod}\ {4}\). Recall that if \(n\equiv 0 \ (\mathrm{mod}\ {4}\), then \(\mathop{\rm maj}(G)=2\) and so \(\mathop{\rm roy}(G)=2\) by Proposition 11 (see [6]. It follows that from Proposition 5 that \(\chi_{\mathop{\rm roy}}(C_n)=3\) for \(n\equiv 0 \\ (\mathrm{mod}\ {4}\). Case \(2\). \(n\equiv 1 \ (\mathrm{mod}\ {4}\). Then \(\mathop{\rm maj}(C_n)=3\) and so \(\mathop{\rm roy}(C_n)=3\) by Proposition 11 (see [6]. For the case of \(n=9\), let a royal \(3\)-edge coloring be given by the color sequence \[s=(\{1\},\{3\},\{1,2\},\{1\},\{3\},\{1,2\},\{1\},\{3\},\{1,2\}).\] The vertex color sequence induced by \(s\) is given by \[s'=(\{1,2\},\{1,3\},[3],\{1,2\},\{1,3\},[3],\{1,2\},\{1,3\},[3]),\] as desired. We may assume \(n\geq 13\). Define a royal \(3\)-edge coloring \(c:E(C_n)\to {\cal P}^*([3])\) of \(C_n\) by \[c(u_iu_{i+1}) = \left\{ \begin{array}{ll} \{1\} & \mbox{ if $i\in\{0,3,6\}$}\\ \{3\} & \mbox{ if $i\in \{1,4,7\}$}\\ \{1,2\} & \mbox{ if $i\in \{2,5\}$ or $i\equiv 0,1\ (\mathrm{mod}\ {4}$ for $8\leq i\leq n-1$}\\ \{1,3\} & \mbox{ if $i\equiv 3,4\ (\mathrm{mod}\ {4}$ for $10\leq i\leq n-2$.} \end{array}\right.\]

Then, the induced coloring \(c':V(C_n)\to {\cal P}^*([3])\) is given by \[c'(u_i) = \left\{ \begin{array}{ll} \{1,2\} & \mbox{ if $i\in \{0,3,6\}$ or $i \equiv 1\ (\mathrm{mod}\ {4}$ for $9\leq i\leq n-4$}\\ \{1,3\} & \mbox{ if $i\in \{1,4\}$ or $i\equiv 3\ (\mathrm{mod}\ {4}$ for $7\leq i\leq n-2$}\\ \{3\}& \mbox{ if $i\in \{2,5\}$ or $i\equiv 0,2\ (\mathrm{mod}\ {4}$ for $8\leq i\leq n-1$.} \end{array}\right.\] Since \(c'\) is a proper \(3\)-coloring of \(C_n\), it follows that \(\chi_{\mathop{\rm roy}}(P_n)=3\) for \(n\equiv 1 \ (\mathrm{mod}\ {4}\), with \(n\geq 9\). Case \(3\). \(n\equiv 2 \ (\mathrm{mod}\ {4}\). Then \(\mathop{\rm maj}(C_n)=3\) and so \(\mathop{\rm roy}(C_n)=3\) by Proposition 11 (see [6]. We may assume \(n\geq 6\). Define a royal \(3\)-edge coloring \(c:E(C_n)\to {\cal P}^*([3])\) of \(C_n\) by \[c(u_iu_{i+1}) = \left\{ \begin{array}{ll} \{1\} & \mbox{ if $i\in\{0,3\}$}\\ \{3\} & \mbox{ if $i= 1$}\\ \{1,2\} & \mbox{ if $i=2$ or $i\equiv 1,2\ (\mathrm{mod}\ {4}$ for $5\leq i\leq n-1$}\\ \{1,3\} & \mbox{ if $i\equiv 0,3\ (\mathrm{mod}\ {4}$ for $4\leq i\leq n-2$.} \end{array}\right.\] Then, the induced coloring \(c':V(C_n)\to {\cal P}^*([3])\) is given by \[c'(u_i) = \left\{ \begin{array}{ll} \{1,2\} & \mbox{ if $i\in \{0,3\}$ or $i \equiv 2\ (\mathrm{mod}\ {4}$ for $6\leq i\leq n-4$}\\ \{1,3\} & \mbox{ if $i=1$ or $i\equiv 0\ (\mathrm{mod}\ {4}$ for $4\leq i\leq n-2$}\\ \{3\}& \mbox{ if $i\in \{2,5\}$ or $i\equiv 0,2\ (\mathrm{mod}\ {4}$ for $5\leq i\leq n-1$.} \end{array}\right.\] Since \(c'\) is a proper \(3\)-coloring of \(C_n\), it follows that \(\chi_{\mathop{\rm roy}}(C_n)=3\) for \(n\equiv 2 \ (\mathrm{mod}\ {4}\), with \(n\geq 6\). Case \(4\). \(n\equiv 3 \ (\mathrm{mod}\ {4}\). Then \(\mathop{\rm maj}(C_n)=3\) and so \(\mathop{\rm roy}(C_n)=3\) by Proposition 11 (see [6]. For the case of \(n=3\), let a royal \(3\)-edge coloring be given by the color sequence \(s=(\{1\},\{3\},\{1,2\})\). The vertex color sequence induced by \(s\) is given by \(s'=(\{1,2\},\{1,3\},[3])\), as desired. We may assume \(n\geq 7\). Define a royal \(3\)-edge coloring \(c:E(C_n)\to {\cal P}^*([3])\) of \(C_n\) by \[c(u_iu_{i+1}) = \left\{ \begin{array}{ll} \{1\} & \mbox{ if $i=0$}\\ \{3\} & \mbox{ if $i= 1$}\\ \{1,2\} & \mbox{ if $i\equiv 2,3\ (\mathrm{mod}\ {4}$ for $2\leq i\leq n-1$}\\ \{1,3\} & \mbox{ if $i\equiv 0,1\ (\mathrm{mod}\ {4}{4}$ for $4\leq i\leq n-2$.} \end{array}\right.\] Then the induced coloring \(c':V(C_n)\to {\cal P}^*([3])\) is given by \[c'(u_i) = \left\{ \begin{array}{ll} \{1,2\} & \mbox{ if $i=0$ or $i \equiv 3\ (\mathrm{mod}\ {4}$ for $3\leq i\leq n-4$}\\ \{1,3\} & \mbox{ if or $i\equiv 1\ (\mathrm{mod}\ {4}$ for $1\leq i\leq n-2$}\\ \{3\}& \mbox{ if $i\equiv 0,2\ (\mathrm{mod}\ {4}$ for $2\leq i\leq n-1$.} \end{array}\right.\] Since \(c'\) is a proper \(3\)-coloring of \(C_n\), it follows that \(\chi_{\mathop{\rm roy}}(C_n)=3\) for \(n\equiv 3 \ (\mathrm{mod}\ {4}\). ◻