Stability in respect of chromatic completion of graphs

1. Introduction

For general notation and concepts in graphs, see [1,2,3]. The set of vertices and the set of edges of a graph \(G\) are denoted by \(V(G),\) \(E(G),\) respectively. The number of vertices is denoted by \(\nu(G)\), and the number of edges of \(G\) is denoted by \(\varepsilon(G).\) Unless stated otherwise, all graphs will be undirected, finite, simple, and connected.

For a set of (distinct) colors \(\mathcal{C}= \{c_1,c_2,c_3,\dots,c_\ell\}\) a vertex coloring of a graph \(G\) is an assignment \(\varphi:V(G) to \mathcal{C}.\) A vertex coloring is said to be a proper vertex coloring of a graph \(G\) if no two distinct adjacent vertices have the same color. The cardinality of a minimum set of distinct colors in a proper vertex coloring of \(G\) is called the chromatic number of \(G\) and is denoted by, \(\chi(G).\) We call such a coloring a \(\chi\)-coloring or a chromatic coloring of \(G.\) A chromatic coloring of \(G\) is denoted by \(\varphi_\chi(G).\) Generally a graph \(G\) of order \(n\) is \(k\)-colorable for \(\chi(G) \leq k \leq n.\)

Generally the set, \(c(V(G))\) is a subset of \(\mathcal{C}\) or put as \(c(V(G)) \subseteq \mathcal{C}.\) A set \(\{c_i \in \mathcal{C}: c(v) = c_i\) for at least one \(v\in V(G)\}\) is called a color class of the coloring of \(G.\) If \(\mathcal{C}\) is the chromatic set it can be agreed that \(c(G)\) means set \(c(V(G))\) hence, \(c(G) to \mathcal{C}\) and \(|c(G)| = |\mathcal{C}|.\) For the set of vertices \(X \subseteq V(G),\) the induced subgraph induced by \(X\) is denoted by, \(\langle X\rangle.\) The coloring of \(\langle X\rangle\) permitted by \(\varphi:V(G) to \mathcal{C}\) is denoted by, \(c(\langle X\rangle).\) The number of times a color \(c_i\) is allocated to vertices of a graph \(G\) is denoted by \(\theta_G(c_i)\) or if the context is clear simply, \(\theta(c_i).\)

Index labeling the elements of a graph such as the vertices say, \(v_1,v_2,v_3,\dots,v_n\) or written as, \(v_i\), \(i = 1,2,3,\dots,n,\) is called minimum parameter indexing. Similarly, a minimum parameter coloring of a graph \(G\) is a proper coloring of \(G\) which consists of the colors \(c_i;\ 1\le i\le \ell.\) All graphs will have index labeled vertices. Only if the context is clear will general references to vertices such as \(u \in V(G)\) or \(v,w \in V(G)\) be used.

This paper is organized as follows. §2 recalls important results of the chromatic completion number of a graph \(G\) from [4]. The concept of stability in respect of chromatic completion of graphs is introduced. A uniqueness theorem in respect of the set of chromatic completion edges denoted by, \(E_\chi(G)\) is also presented. §3 addresses chromatic completion and stability of a graph in respect of Johan colorings. §4 concludes this paper by discussing results for two elementary graph operations.

2. Stability

In an improper coloring an edge \(uv\) for which, \(c(u)=c(v)\) is called a bad edge. See [5] for an introduction to \(k\)-defect coloring and corresponding polynomials. For a color set \(\mathcal{C},\) \(|\mathcal{C}| \geq \chi (G)\) a graph \(G\) can always be colored properly hence, such that no bad edge results. Also, for a set of colors \(\mathcal{C},\) \(|\mathcal{C}| = \chi (G) \geq 2\) a graph \(G\) of order \(n\) with corresponding chromatic polynomial \(\mathcal{P}_G(\lambda, n),\) can always be colored properly in \(\mathcal{P}_G(\chi, n)\) distinct ways. Hence, chromatic coloring of a graph is generally not a unique coloring.

The notion of the chromatic completion number of a graph \(G\) denoted by, \(\zeta(G)\) is the maximum number of edges over all chromatic colorings that can be added to \(G\) without adding a bad edge [4]. The resultant graph \(G_\zeta\) is called a chromatic completion graph of \(G.\) The additional edges are called chromatic completion edges. It is trivially true that \(G\subseteq G_\zeta.\) Clearly for a complete graph \(K_n,\) \(\zeta(K_n)=0.\) In fact for any complete \(\ell\)-partite graph \(H=K_{n_1,n_2,n_3,\dots,n_\ell},\) \(\zeta(H)=0.\) Hereafter, all graphs will not be \(\ell\)-partite complete. For graphs \(G\) and \(H\) both of order \(n\) with \(\varepsilon(G)\geq \varepsilon(H)\) no relation between \(\zeta(G)\) and \(\zeta(H)\) could be found. We state the following six important results from [4], which form a basis of this paper.

Theorem 1.\([10]\) A graph \(G\) of order \(n\) is not complete, if and only if \(G_\zeta\) is not complete.

Lemma 2.\([10]\) For a chromatic coloring \(\varphi:V(G) to \mathcal{C}\) a pseudo completion graph, \(H(\varphi)= K_{n_1,n_2,n_3,\dots,n_\chi}\) exists such that, \[\varepsilon(H(\varphi))-\varepsilon(G) =\sum\limits_{i=1}^{\chi-1}\theta_G(c_i)\theta_G(c_j)_{(j=i+1,i+2,i+3,\dots,\chi)}-\varepsilon(G) \leq \zeta(G).\]

A main result in the form of a corollary is a direct consequence of Lemma 2.

Corollary 3.\([10]\) Let \(G\) be a graph. Then \begin{eqnarray*} \zeta(G) & = & max\{\varepsilon(H(\varphi)) -\varepsilon(G):\text{over all} \ \varphi:V(G) to \mathcal{C}\}. \end{eqnarray*}

Theorem 4.\([10]\) Let \(G\) be a graph. Then \(\zeta(G)\leq \varepsilon(\overline{G}).\)

If for all chromatic colorings of \(G\) we have that, \(\theta(c_i)\geq 2\) for some \(c_i\) then, \(\zeta(G) < \varepsilon(\overline{G})\). Hence, equality holds if and only if a graph \(G\) of order \(n\) is complete.

Theorem 5.[Lucky’s Theorem][4] For a positive integer \(n \geq 2\) and \(2\leq p \leq n\) let integers, \(1\leq a_1,a_2,a_3,\dots,a_{p-r}, a’_1,a’_2,a’_3,\dots,a’_r \leq n-1\) be such that \(n=\sum\limits_{i=1}^{p-r}a_i + \sum\limits_{j=1}^{r}a’_j\) then, the \(\ell\)-completion sum-product \(\mathcal{L} = max\{\sum\limits_{i=1}^{p-r-1}\prod\limits_{k=i+1}^{p-r}a_ia_k + \sum\limits_{i=1}^{p-r}\prod\limits_{j=1}^{r}a_ia’_j + \sum\limits_{j=1}^{r-1}\prod\limits_{k=j+1}^{r}a’_ja’_k\}\) over all possible, \(n=\sum\limits_{i=1}^{p-r}a_i + \sum\limits_{j=1}^{r}a’_j.\)

From Theorem 5 the next lemma followed which prescribes a particular coloring convention.

Lemma 6.\([10]\) If a subset of \(m\) vertices say, \(X \subseteq V(G)\) can be chromatically colored by \(t\) distinct colors then allocate colors as follows:

• For \(t\) vertex subsets each of cardinality \(s= \lfloor \frac{m}{t}\rfloor\) allocate a distinct color followed by:
• Color one additional vertex (from the \(r\geq 0\) which are uncolored), each in a distinct color,

if the graph structure permits such color allocation. This chromatic coloring permits the maximum number of chromatic completion edges between the vertices in \(X\) amongst all possible chromatic colorings of \(X\).

It is known that for a graph which does not permit a color allocation as prescribed in Lemma 6, an optimal near-completion \(\ell\)-partition of the vertex set exists which yields the maximum chromatic completion edges, [4]. Note that the coloring in accordance with Lemma 6 is essentially a special case of an optimal near-completion \(\ell\)-partition of the vertex set \(V(G).\) Henceforth, a chromatic coloring in accordance with either Lemma 6 or an optimal near-completion \(\ell\)-partition will be called a Lucky coloring denoted by, \(\varphi_{\mathcal{L}}(G).\) If all possible Lucky colorings of a graph \(G,\) yield identical vertex partitions then graph \(G\) is said to be, stable in respect of chromatic completion. Such graph is denoted to be, \(SCC.\) It means that if \(\chi(G)\geq 2,\) the different Lucky colorings only effect pairwise interchange of color classes. Such different colorings are said to be congruent and is denoted by, \(\varphi_{\mathcal{L}}(G)_1 \cong \varphi_{\mathcal{L}}(G)_2.\) For all graphs for which \(\zeta(G)=0\) it follows that \(E_\chi(G) =\emptyset\) and therefore, inherently unique. All such graphs are inherently \(SCC.\) Unless mentioned otherwise, graphs for which \(\zeta(G) > 0\) will be considered hereafter.

Theorem 7. For a graph \(G\), \(\zeta(G) > 0\) is \(SCC\) if and only if the chromatic completion edge set \(E_\chi(G)\) is unique.

Proof. Let the vertices of a graph \(G\) of order \(n\geq 1\) be, \(v_i\), \(i=1,2,3,\dots, n.\) Assume that the chromatic completion edge set \(E_\chi(G)\) is unique. Then all possible Lucky colorings of \(G\) yield identical vertex partitions with only possible interchange of color classes. By definition \(G\) is \(SCC.\)

Converse: Assume that \(G\) is \(SCC\) the vertex partitions over all possible Lucky colorings are identical. Since, \(\zeta(G)>0\) at least one edge \(v_iv_j\in E_\chi(G)\) exists. It means that, if for any given Lucky coloring the edge \(v_iv_j \in E_\chi(G)\) then, \(v_iv_j \notin E(G)\) and \(c(v_i)\neq c(v_j).\) It also means that in any other Lucky coloring, \(c(v_j)\neq c(v_j)\). Hence, \(v_iv_j \in E_\chi(G)\) over all Lucky colorings. Therefore, \(E_\chi(G)\) is unique.

Corollary 8. For a graph \(G,\) \(\zeta(G) > 0,\) the chromatic completion edge set \(E_\chi(G),\) is unique if \(G\) is \(2\)-colorable.

Proof. Consider any \(2\)-colorable graph \(G,\) \(\zeta(G) > 0.\) The vertex set can be partitioned in two unique subsets. Only two Lucky colorings are possible i.e. interchanging colors \(c_1\) and \(c_2\). Hence, \(G\) is \(SCC.\) By Theorem 7 the result follows.

Corollary 9. A graph \(G,\) \(\chi(G)\geq 3\) which has a pendant vertex is not \(SCC.\)

Proof. Let \(u\) be a pendant vertex and assume without loss of generality that, \(c(u)=c_1.\) Also assume \(u\) is adjacent to vertex \(v\) and \(c(v)=c_2.\) Since \(\chi(G)\geq 3\) a vertex \(w \in V(G)\) exists with \(c(w)=c_j,\) \(j\neq 1,2\) and edge \(uw\notin E(G).\) Obviously the color interchange \(c(u)=c_j\) and \(c(w)=c_1\) is possible and the coloring remains a Lucky coloring. Also, \(\zeta(G)\) remains constant. Whereas before the color interchange, edges \(uw’ \in E_\chi(G),\) \(\forall w’\in \{v’:c(v’)=c_j, v’\neq w\},\) these edges do not exist after the color change. Hence, not all Lucky colorings yield identical vertex partitions. Thus, \(G\) is not \(SCC.\)

For any proper coloring of a graph with \(k\) colors the vertex set can be partitioned into \(k\) independent subsets say, \(X_i,\) \(i=1,2,3,\dots,k.\) It is obvious that \(c(X_i)\neq c(X_j)\) if and only if \(i\neq j.\) Call these vertex subsets, chromatic vertex subsets of \(V(G).\)

Theorem 10. A graph \(G\), \(\zeta(G)>0\) is \(SCC\) if and only if for any Lucky coloring the chromatic vertex subsets, \(X_i\), \(i=1,2,3,\dots,\chi(G)\) are such that every vertex \(v\in X_i\), \(\forall i\) is adjacent to at least one vertex \(u\in X_j\), \(j=1,2,3,\dots,i-1,i+1,\dots,\chi(G)\).

Proof. For a graph \(G\) for which a Lucky coloring exists such that the chromatic vertex subsets, \(X_i\), \(i=1,2,3,\dots,\chi(G)\) are such that every vertex \(v\in X_i\), \(\forall i\) is adjacent to at least one vertex \(u\in X_j\), \(j=1,2,3,\dots,i-1,i+1,\dots,\chi(G)\) implies that identical vertex partitions are yielded for all Lucky colorings. Hence, \(G\) is \(SCC\).

Conversely, let \(G\) be \(SCC\). Consider a Lucky coloring and its corresponding chromatic vertex subsets, \(X_i\), \(i=1,2,3,\dots,\chi(G)\). If a vertex \(v\in X_i\) exists such that \(v\) is not adjacent to any vertex in say, \(X_j\), \(i\neq j\) then \(v\) may be colored \(c(X_j)\) whilst \(\zeta(G)\) remains unchanged. Now the chromatic vertex subsets changed to include \(X_i\backslash v\) and \(X_j\cup\{v\}\). It implies that \(G\) is not \(SCC\) which is a contradiction. Hence, \(v\) must be adjacent to at least one vertex \(v_j\in X_j\), \(\forall j\), \(j=1,2,3,\dots,i-1,i+1,\dots,\chi(G)\).

An important implication is that a graph \(G\) which satisfies the conditions of Theorem 10 in respect of its chromatic vertex subsets has a unique set of chromatic completion edges.

Recall that the rainbow neighborhood convention prescribed that we color the vertices of a graph \(G\) in such a way that \(\mathcal{C}_1=I_1,\) the maximal independent set in \(G,\) \(\mathcal{C}_2=I_2,\) the maximal independent set in \(G_1=G-\mathcal{C}_1\) and proceed like this until all vertices are colored [6,7,8]. In [6] the concept of a rainbow neighborhood yielded by vertex \(u\) in graph \(G\) was introduced. It is important to note that the graph \(G\) had to be colored in accordance to the rainbow neighborhood convention to determine the rainbow neighborhood number, \(r_\chi(G)\) of a graph \(G.\) Hence, well-defined coloring conventions may serve to generalize the concept of the rainbow neighborhood number i.e. the number of vertices which yield rainbow neighborhoods in \(G.\) The rainbow neighborhood number associated with a Lucky coloring of a graph \(G\) will be denoted by, \(r_{\mathcal{L}}(G).\)

Theorem 11. A graph \(G\) is \(SCC\) if and only if for a Lucky coloring of \(G,\) \(r_{\mathcal{L}}(G)=|V(G)|=\nu(G).\)

Proof. If \(r_{\mathcal{L}}(G)=|V(G)|=\nu(G)\) then every vertex is adjacent to at least one colored vertex of each color in a Lucky coloring of \(G\). By Theorem 10 it follows that \(G\) is \(SCC.\)

Conversely, if \(G\) is \(SCC\) then by Theorem 10 the result follows.

Since a Lucky coloring is a relaxation of the rainbow neighborhood convention it follows that if a graph is \(SCC\) in respect of a coloring in accordance with the rainbow neighborhood convention, it is \(SCC\) in accordance with a Lucky coloring. In fact, it follows that in respect of such \(G\) both coloring conventions are congruent colorings. See [6,7,8,9] for further results in respect of rainbow neighborhood numbers.

3. Chromatic completion and stability in respect of \(\mathcal{J}\)-coloring

Thus far the notion of chromatic completion of a graph related strictly to chromatic colorings by the convention of Lucky colorings. This requirement can be relaxed to generalize over all chromatic colorings \(\varphi_\chi(G).\) Clearly, we have by analogy that, \(\zeta_\varphi(G)\leq \zeta(G).\) We further generalize to a recently introduced coloring convention called Johan coloring or \(\mathcal{J}\)-coloring [10,11,12,13]. The chromatic completion edge set denoted by \(E_{\mathcal{J}}(G),\) will be investigated. Corresponding to a \(\mathcal{J}\)-coloring the cardinality of the chromatic completing edge set is denoted by, \(\zeta_{\mathcal{J}}(G) = |E_{\mathcal{J}}(G)|.\) Recall the definition from [13].

Definition 12. A maximal proper coloring of a graph \(G\) is a Johan coloring of \(G,\) denoted by \(\mathcal{J}\)-coloring, if and only if every vertex of \(G\) yields a rainbow neighborhood of \(G\). The maximum number of colors in a \(\mathcal{J}\)-coloring is called the \(\mathcal{J}\)-chromatic number of \(G,\) denoted by \(\mathcal{J}(G).\)

Recall that not all graphs permit a \(\mathcal{J}\)-coloring [13]. Unless stated otherwise, all graphs in this subsection will permit a \(\mathcal{J}\)-coloring. Figure 1 depicts a graph with a Lucky coloring with \(\chi(G)=2\) colors. It is easy to verify that \(\zeta(G)=4.\) Figure 2 depicts the same graph with a \(\mathcal{J}\)-coloring with \(\mathcal{J}(G)=4\) colors. Note that the \(\mathcal{J}\)-coloring complies with the color allocations of Lemma 6. It is easy to verify that, \( \zeta_{\mathcal{J}}(G)=|E_{\mathcal{J}}(G)|=12.\) The aforesaid serves as an illustration of the next result.

Proposition 13. For a graph \(G\) it follows that, \(\zeta_\varphi(G) \leq \zeta(G)\leq \zeta_{\mathcal{J}}(G).\)

Proof. That \(\zeta_\varphi(G) \leq \zeta(G)\) holds follows directly from Theorem 5. The result \(\zeta(G)\leq \zeta_{\mathcal{J}}(G)\) is a direct consequence of the number theoretical result (or optimal near-completion \(\ell\)-partition) as the number of colors i.e. \(\ell,\) increases whilst the order of \(G\) remains constant.

Proposition 13 can informally be understood by saying, that if for a particular Lucky coloring, some vertices in some color classes are allocated new colors, then more edges are permitted in terms of the definition of chromatic completion of a graph.

Theorem 14. For a graph \(G\) it follows that, \(\zeta_\varphi(G) = \zeta(G)= \zeta_{\mathcal{J}}(G)\) if and only if \(\varphi_\chi(G) \cong \varphi_{\mathcal{L}}(G) \cong \varphi_{\mathcal{J}}(G).\)

Proof. If \(\varphi_\chi(G) \cong \varphi_{\mathcal{L}}(G) \cong \varphi_{\mathcal{J}}(G)\) it follows trivially that, \(\zeta_\varphi(G) = \zeta(G)= \zeta_{\mathcal{J}}(G).\)

If \(\zeta_\varphi(G) = \zeta(G)= \zeta_{\mathcal{J}}(G)\) it follows from Theorem 10 that, \(\varphi_\chi(G) \cong \varphi_{\mathcal{L}}(G) \cong \varphi_{\mathcal{J}}(G).\)

The next corollaries are direct consequences of Theorem 14.

Corollary 15. For a graph \(G\) equality holds in accordance with Proposition 13 if and only if \(G\) is \(SCC\) in respect of a proper coloring.

Corollary 16. \(E_\varphi(G) is unique,\) implies that \(E_{\mathcal{L}}(G) is unique,\) implies that \(E_{\mathcal{J}}(G) is unique.\)

An example is that, the alternating coloring \(c(v_i)=c_1, c(v_{i+1})=c_2,\) \(i=1,2,3,\dots, n-1\) of the vertices of an even cycle graph, \(C_n,\) \(n\geq 4\) is firstly, a \(\mathcal{J}\)-coloring because it is a maximal proper coloring with each vertex yielding a rainbow neighborhood in \(C_n.\) It follows easily that the coloring is indeed a Lucky coloring followed by the implication that it is a chromatic coloring. Clearly, for all three coloring conventions the even cycle graph is \(SCC\) as well as, \( E_\varphi(G) = E_{\mathcal{L}}(G)= E_{\mathcal{J}}(G).\) and unique to \(C_n,\) \(n\geq 4,\) \(n\) even.

Since any graph \(G\) is \(k\)-colorable for some \(k\geq 1\) it is chromatic colorable. Therefore, it permits a Lucky coloring. However not all graphs permit a \(\mathcal{J}\)-coloring. This observation leads to the next result.

Theorem 17. A graph \(G\) which does not permit a \(\mathcal{J}\)-coloring is not \(SCC.\)

Proof. A graph \(G\) which does not permit a \(\mathcal{J}\)-coloring has for all proper colorings, including all Lucky colorings, a corresponding color class vertex partition such that a vertex \(v,\) \(c(v)=c_i\) exists which is not adjacent to at least one vertex in each color class \(\mathcal{C}_j\), \(j=1,2,3,\dots,i-1,i+1,\dots,\chi(G).\) Hence, by Theorem 10, \(G\) is not \(SCC.\)

Put differently, Theorem 17 implies that the set of \(SCC\) graphs is a subset of the set of \(\mathcal{J}\)-colorable graphs. As example, it follows that any graph \(G\) which contains an odd cycle of length \(n\geq 5\) and \(n\equiv1 or 2 (mod 3)\) is not \(SCC.\) See [13] for \(\mathcal{J}\)-colorable results on odd cycle graphs.

4. Elementary Graph Operations

In this subsection the disjoint union and the join of graphs \(G\) and \(H\) are considered. In the disjoint union operation between graphs \(G\) and \(H\) the respective values, \(\zeta(G)\) and \(\zeta(H)\) remain the same if \(\varphi_{\mathcal{L}}(G),\), \(\varphi_{\mathcal{L}}(H)\) remain the same. The term \(\sum\limits_{i=1}^{\chi(G)}\prod\limits_{j=1}^{\chi(H)}\theta_G(c_i)\theta_H(c_j)_{i\neq j}\) follows from the definition of chromatic completion of a graph.

Proposition 18. For graphs \(G\) and \(H\) it follows that, \(\zeta(G\cup H) \geq \zeta(G)+\zeta(H) + \sum\limits_{i=1}^{\chi(G)}\prod\limits_{j=1}^{\chi(H)}\theta_G(c_i)\theta_H(c_j)_{i\neq j}.\)

Proof. For \(\varphi_{\mathcal{L}}(G)\) and \(\varphi_{\mathcal{L}}(H)\) it is possible (not necessarily) to find a pair of vertices \(u,v \in V(G)\) such that \(c(u)=c(v)\) in \(G\) but \(c(u)\neq c(v)\) in \(G\cup H.\) Therefore, the edge \(uv \in E_\chi(G\cup H)\) but \(uv\notin E_\chi(G).\) Similarly in \(H.\) It is also possible (not necessarily) to find a pair of vertices \(u\in V(G),\) \(v\in V(H)\) such that \(c(u)=c(v)\) in \(G\) and \(H\) respectively, but \(c(u)\neq c(v)\) in \(G\cup H.\) Therefore, the edge \(uv \in E_\chi(G\cup H).\) Hence, \(\zeta(G\cup H) \geq \zeta(G)+\zeta(H) + \sum\limits_{i=1}^{\chi(G)}\prod\limits_{j=1}^{\chi(H)}\theta_G(c_i)\theta_H(c_j)_{i\neq j}.\)

The complexity to improve on the lower bound of Proposition 13 stem from the facts that firstly, \(\chi(G\cup H) = max\{\chi(G), \chi(H)\}\) and secondly, that the value \(\chi(G\cup H)\) must be applied to \(\nu(G\cup H)=\nu(G)+\nu(H)\) vertices to find an appropriate optimal near-completion \(\ell\)-partition.

Conjecture 1. If both graphs \(G,\) \(H\) permit a Lucky coloring as prescribed in accordance to Theorem 6 and Lemma 6 then, \(\zeta(G\cup H) = \zeta(G)+\zeta(H) + \sum\limits_{i=1}^{\chi(G)}\prod\limits_{j=1}^{\chi(H)}\theta_G(c_i)\theta_H(c_j)_{i\neq j}.\)

The graph \((G-E(G))+(H-E(H))\) is a spanning subgraph of \(G+H\) and chromatic completion does not result in additional edges \(uv\), \(u\in V(G)\), \(v\in V(H).\) Since \(\chi(G+H)=\chi(G)+\chi(H)\) with colors say, \(\mathcal{C}=\{c_1,c_2,c_3,\dots,c_{\chi(G)}, c_{\chi(G)+1}, c_{\chi(G)+2}, c_{\chi(G)+3},\dots, c_{\chi(G)+\chi(H)}\},\) the values \(\zeta(G)\) and \(\zeta(H)\) remain the same in the join operation between graphs \(G\) and \(H.\) Hence, \(\zeta(G+H) = \zeta(G)+\zeta(H)\) for all graphs. It thus follows that \(\zeta(K_1+ H)= \zeta(H)\). Despite this trivial observation it is hard to find \(\zeta(G\circ H)\) in general, where \(G\circ H\) denote the corona graph.

Corollary 19. \(G\) and \(H\) are \(SCC\) if and only if \(G + H\) is \(SCC.\)

Proof. If \(G+H\) is \(SCC\) then a vertex \(v\in V(G)\), \(c(v)=c_i\) is adjacent to at least one vertex \(u\), \(c(u)=c_j,\) \(j= 1,2,3,\dots i-1,i+1,\dots, \chi(G)+\chi(H).\) Therefore, \(v\in V(G),\) \(c(v)=c_i\) is adjacent to at least one vertex \(u \in V(G+H),\) \(c(u)=c_j,\) \(j= 1,2,3,\dots i-1,i+1,\dots, \chi(G)+\chi(H).\) Hence, \(v\in V(G),\) \(c(v)=c_i\) is adjacent to at least one vertex \(u \in V(G),\) \(c(u)=c_j,\) \(j= 1,2,3,\dots i-1,i+1,\dots, \chi(G).\) Thus, by Theorem 10, \(G\) is \(SCC.\) Similarly it follows that \(H\) is \(SCC.\)

Conversely, if both \(G\) and \(H\) are \(SCC\) the join operation implies that \(uv\in E(G+H),\) \(\forall\) distinct pairs \(u\in V(G),\) \(v\in V(H).\) Hence, \(G+H\) is \(SCC.\) Clearly, if say \(G\) is not \(SCC\) and \(H\) is \(SCC\) then, by Theorem 10, \(G+H\) is not \(SCC\) because there exists at least one vertex \(v\in V(G),\) \(c(v)=c_i\) which is not adjacent to at least one vertex colored \(c_j,\) \(1,2,3,\dots i-1,i+1,\dots, \chi(G).\)

Proposition 18 read together with \(\zeta(G+H) = \zeta(G)+\zeta(H)\) implies that, \(\zeta(G\cup H) \geq \zeta(G+H).\)

5. Conclusion

Lucky’s theorem read with Lemma 2 allows for the determination of an upper bound of \(\zeta(G)\). Note that for two proper colorings say, \(\varphi:V(G) to \mathcal{C}\), \(|\mathcal{C}|=k\) and \(\varphi’:V(G) to \mathcal{C}’\), \(|\mathcal{C}’| =k+t\), \(1\leq t\leq n-k\), which are both allocated according to Lemma 6 or as a near-completion \(k\)-partition and a near-completion \((k+t)\)-partition respectively, then \(\varepsilon(G_{{\varphi}’}) \geq \varepsilon(G_\varphi)\), where \(\varepsilon(G_{{\varphi}’})\), \(\varepsilon(G_\varphi)\) denote the respective proper coloring completion graphs. The aforesaid leads to the following algorithm which provides an upper bound on \(\zeta(G)\). For the purpose of the algorithm we utilize a deviation of the minimum parameter indexing of the vertices.

5.1. Near-Lucky proper coloring of graph \(G\)

Consider a graph \(G\) of order \(n\geq 1\) with vertices \(v_i\), \(i=0, 1,2,\dots, n-1\) such that, \(d(v_0)\geq d(v_1)\geq d(v_2)\geq\cdots\geq d(v_{(n-1)})\). Let \(\varphi :V(G) to \mathcal{C}\), \(\mathcal{C} =\{c_0,c_1,c_2,\dots,c_{(\chi(G)-1)}\}\) be a chromatic coloring of \(G\).

Step 1: Let \(j=1\), \(\mathcal{C}_j = \mathcal{C}\) and \(i=j\). Go to step 2.

Step 2: Let \(\mathcal{C}_i = \mathcal{C}_j\). Color \(v_i\), \(c(v_i)=c_i (mod \chi(G))\) if possible, alternatively any permissible color \(c_t \in \mathcal{C}_i\) if possible. Else, color with an additional color \(c_i’\notin \mathcal{C}_i\) and let \(\mathcal{C}_j= \mathcal{C}_i\cup \{c’_i\}\). Go to step 3.

Step 3: Let \(j=i+1\). If \(j > n-1\), go to step 4. Else, let \(i=j\). Go to step 2.

Step 4: Let \(\varphi’:V(G) to \mathcal{C}_i\) and stop.

Clearly the algorithm converges in finite time. The result is \(|\mathcal{C}_n|\geq |\mathcal{C}|\). Hence, it follows easily from Lucky’s theorem read with Lemma 2 that, \(\zeta(G)=\zeta_{\varphi}(G) \leq \zeta_{\varphi’}(G)\). It is easy to verify that the algorithm results in an exact Lucky coloring for all cycle graphs, \(C_n\), \(n\geq 3\) if the vertices are consecutively labeled. Hence, the upper bound is best possible if a Lucky coloring results. Improving the efficiency of the algorithm remains open. The authors suggest that for graphs in general, coloring \(v_i\) followed by coloring \(N(v_i)\), \(i\in \{0,1,2,\dots, n-1\}\) until all vertices have been colored is a worthy avenue of research.

Improving the upper bound in Theorem 4 for graphs which are not complete, remains open.

Theorem 10 characterizes graphs which are \(SCC.\) Finding well-defined families of graphs that are \(SCC\) remains open and is certainly worthy of further research. Furthermore, if a graph \(G\) is \(SCC\) it implies that for all lucky colorings, the corresponding chromatic completions graphs are isomorphic. However, it is possible to find graphs that are not \(SCC\), but up to isomorphism, the chromatic completion graphs remain equivalent. For the graphs above, the vertices might require relabeling. Finding such graphs remains open for research.

The difficulty seen with the disjoint union signals that advanced graph operations such as the various graph products, graph powers, derivative corona’s, and others permit worthwhile research. Finding a Lucky coloring for a given graph \(G\) remains an open problem. Characterizing graphs \(G,\) \(H\) such that \(G\circ H\) is \(SCC\) and doing the same for other graph operations remain open problems.

Author Contributions:

All authors contributed equally in this paper. All authors read and approved the final version of this paper.

Conflicts of Interest:

The authors declare no conflict of interest.

Acknowledgments :

The author would like to thank the anonymous referees for their constructive comments, which helped to improve on the elegance of this paper.