Coloring of $n$-inordinate invariant intersection graphs

Proof. Note that $\omega ({\mathrm{\Lambda }}_{K_n}^{\ast })=\chi ({\mathrm{\Lambda }}_{K_n}^{\ast })=(n-1)!\le {\chi }_{ach}({\mathrm{\Lambda }}_{K_n}^{\ast })$. If possible, assume that there exists a complete coloring $c:V({\mathrm{\Lambda }}_{K_n}^{\ast })\to \{c_1,c_2,\dots ,c_{(n-1)!+1}\}$ of ${\mathrm{\Lambda }}_{K_n}^{\ast }$. This implies that all $(\genfrac{}{}{0ex}{}{(n-1)!+1}{2})$ pairs of colors appear on at least one pair of adjacent vertices.

Let $c(v_{{\pi }_1})=c_{(n-1)!+1}$, for some $v_{{\pi }_1}\in V({\mathrm{\Lambda }}_{K_n}^{\ast })$. Based on the adjacency pattern of vertices in the graph ${\mathrm{\Lambda }}_{K_n}$, any vertex in $V_i^1$; $1\le i\le n$, is a part of exactly one clique of order $(n-1)!$, which is induced by the corresponding $V_i$ and these vertices are adjacent to exactly $(n-1)!-1$ vertices of that clique. Without loss of generality, select $V_1$ for further analysis, as the choice of any $V_i$ does not affect the adjacency pattern of vertices in the maximal cliques induced. As all $(n-1)!$ vertices in $V_1$ are distinctly colored, $v_{{\pi }_1}\notin V_1$. Also, any vertex in $V_i^1$ is adjacent to only $(n-1)!-1$ vertices in ${\mathrm{\Lambda }}_{K_n}$ and hence $v_{{\pi }_1}\notin V_i^1$; for any $1\le i\le n$.

On assigning $(n-1)!$ colors to the vertices of $V_1$, the number of vertices in $V_i–V_1$, for any $2\le i\le n$, that are to be colored, is less than $(n-1)!$. Also, the cardinality of the sets $V_i–\bigcup _{j=1}^{i-1}{V}_j$, for $1\le i\le n$, in order, decrease from $(n-1)!$ to $\rho (n-1)$, as the $V_i$’s are non-disjoint and hence a vertex corresponding to a permutation having the least possible cardinality of fix is adjacent to the maximum possible vertices in $V_i–\bigcup _{j=1}^{i-1}{V}_i$, for any $1\le i\le n$. Therefore, any vertex $v_{(t_1)(t_2)};2\le t_1\ne t_2\le n$, can be assigned the color $c_{(n-1)!+1}$, as they have the same degree and the vertex $v_{(t_1)(t_2)}$ is adjacent to all other vertices of ${\mathrm{\Lambda }}_{K_n}$ that corresponds to permutations that fix either $t_1$ or $t_2$. Therefore, without loss of generality, assume that the vertex $v_{(2)(3)}$ is assigned the color $c_{(n-1)!+1}$. Since $v_{(2)(3)}$ is not adjacent to all $(n-1)!$ vertices of $V_1$, the colors assigned to the vertices of $V_1$ to which $v_{(2)(3)}$ is not adjacent to must be assigned to the vertices of either $V_2–V_1$ or $V_3–(V_1\cup V_2)$. Since $|V_2–V_1|+|V_3–(V_1\cup V_2)|<|V_1|$, even if all these vertices in $V_2–V_1$ or $V_3–(V_1\cup V_2)$ are given distinct colors, there shall not exist any edge having the end vertices colored with the pair $c_{(n-1)!+1}$, $c_t$; for some $1\le t\le (n-1)!$, yielding a contradiction. Hence, ${\chi }_{ach}({\mathrm{\Lambda }}_{K_n}^{\ast })=(n-1)!$. The same coloring can be extended to the graph ${\mathrm{\Lambda }}_{K_n}$, as the other components apart from ${\mathrm{\Lambda }}_{K_n}^{\ast }$ are trivial. 

Proof. As the graph ${\overline{\mathrm{\Lambda }}}_{K_n}$ has $\omega ({\overline{\mathrm{\Lambda }}}_{K_n})=\chi ({\overline{\mathrm{\Lambda }}}_{K_n})=\rho (n)+n$, ${\chi }_{ach}({\overline{\mathrm{\Lambda }}}_{K_n})\ge \rho (n)+n$. Conversely, assume that ${\chi }_{ach}({\overline{\mathrm{\Lambda }}}_{K_n})=\rho (n)+n+1$ and let $c$ be such a complete coloring of ${\overline{\mathrm{\Lambda }}}_{K_n}$ with $\rho (n)+n+1$ colors, say $c_1,c_2,\dots ,c_{\rho (n)+n+1}$. As every complete coloring is proper, the clique of order $\rho (n)+n$ induced by the $\rho (n)$ universal vertices along with each set of $n$ vertices with distinct fix in $V_i^1;1\le i\le n$, vertices must be colored with distinct colors.

Therefore, assign the color $c_i;1\le i\le n$, to the vertices of $V_i^1$, for the corresponding $1\le i\le n$, and the colors $c_i;n+1\le i\le \rho (n)+n$, to the $\rho (n)$ universal vertices. For $c$ to be a complete coloring of ${\overline{\mathrm{\Lambda }}}_{K_n}$, the color $c_{\rho (n)+n+1}$ has to be assigned to any vertex $v_{\pi }\in V_i^k$; $1\le i\le n$, and $2\le k\le n-2$, as $v_{{\pi }_0}$ is adjacent to only the $\rho (n)$ universal vertices and the subgraph of ${\overline{\mathrm{\Lambda }}}_{K_n}$ induced by $\bigcup _{i=1}^n{V}_i^1$ is a complete $n$-partite graph, with each partite having $\rho (n-1)$ vertices.

Let $c(v_{\pi })=c_{\rho (n)+n+1}$, for some $\pi$ with $2\le |\mathrm{f}\mathrm{i}\mathrm{x}(\pi )|\le n-2$. Therefore, $v_{\pi }\in V_{t_1}\cap V_{t_2}$, for some $1\le t_1<t_2\le n$. As $v_{\pi }$ is not adjacent to the vertices of $V_{t_1}\cup V_{t_2}$, some vertex of $V_i–(V_{t_1}\cup V_{t_2})$; $1\le i\ne t_1\ne t_2\le n$, must be assigned the colors $c_{t_1}$ and $c_{t_2}$ to satisfy the complete coloring protocol. This assignment cannot be done because all the vertices of $V_i–(V_{t_1}\cup V_{t_2})$; $1\le i\ne t_1\ne t_2\le n$, are adjacent to all the vertices of $V_{t_1}^1$ and $V_{t_2}^1$, which are colored using the colors $c_{t_1}$ and $c_{t_2}$, respectively. Hence, ${\chi }_{ach}({\overline{\mathrm{\Lambda }}}_{K_n})<n+\rho (n)+1$; completing the proof. 

Proof. As $v_{{\pi }_0}$ is a universal vertex of the graph ${\mathrm{\Lambda }}_{K_n}^{\ast }$, we need $n!-\rho (n)$ colors in order to obtain an exact coloring with respect to the color assigned to $v_{{\pi }_0}$. For ${\mathrm{\Lambda }}_{K_n}^{\ast }$ to have exactly one edge having end vertices with all $(\genfrac{}{}{0ex}{}{n!-\rho (n)-1}{2})$ pairs of colors, ${\mathrm{\Lambda }}_{K_n}^{\ast }$ must be a complete graph, which cannot happen for any $n\ge 1$. Therefore, the graphs ${\mathrm{\Lambda }}_{K_n}^{\ast }$ and ${\mathrm{\Lambda }}_{K_n}$ do not admit an exact coloring. Using the similar argument based on the existence of $\rho (n)$ universal vertices in ${\overline{\mathrm{\Lambda }}}_{K_n}$, it can be proved that ${\overline{\mathrm{\Lambda }}}_{K_n}$ also does not admit an exact coloring. 

Proof. The graph ${\mathrm{\Lambda }}_{K_n}^{\ast }$ contains a universal vertex $v_{{\pi }_0}$, and hence every vertex in ${\mathrm{\Lambda }}_{K_n}^{\ast }$ must be given a unique color to obtain a harmonious coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$. If there exists two vertices given the same color, it violates the definition of a harmonious coloring as two edges will have the same pair of colors on its end vertices. Hence, ${\chi }_h({\mathrm{\Lambda }}_{K_n}^{\ast })=n!-\rho (n)$. Also, any harmonic coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ can be extended as the harmonic coloring of ${\mathrm{\Lambda }}_{K_n}$, by assigning any of the $n!-\rho (n)$ colors used to color the vertices of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ to the $\rho (n)$ isolated vertices of ${\mathrm{\Lambda }}_{K_n}$, as the isolated vertices do not contribute to any edges in the graph. Therefore, ${\chi }_h({\mathrm{\Lambda }}_{K_n}^{\ast })={\chi }_h({\mathrm{\Lambda }}_{K_n})=n!-\rho (n)$. The proof of (ii) follows immediately based on the arguments of (i), as there are $\rho (n)$ universal vertices in ${\overline{\mathrm{\Lambda }}}_{K_n}$. 

Proof. According to the injective coloring protocol, if a vertex of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ and its neighbour has to be given the same color, it can only be $v_{{\pi }_0}$ and one of its neighbour, say $v_{\pi }$, as $v_{{\pi }_0}$ is a universal vertex in the graph ${\mathrm{\Lambda }}_{K_n}^{\ast }$. Any neighbour $v_{{\pi }^{\mathrm{\prime }}}$ of $v_{\pi }$ is a neigbour of $v_{{\pi }_0}$, and hence this assignment will conflict the injective coloring protocol as two vertices in the neighbourhood $v_{{\pi }^{\mathrm{\prime }}}$ will have the same color. Therefore, any injective coloring of the graph ${\mathrm{\Lambda }}_{K_n}^{\ast }$ is a proper coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$, which demands the assignment of unique colors to all its vertices. Any injective coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ is also an injective coloring of ${\mathrm{\Lambda }}_{K_n}$, as the $\rho (n)$ trivial components do not have neighbours to alter the coloring protocol. Hence, ${\chi }_i({\mathrm{\Lambda }}_{K_n}^{\ast })={\chi }_i({\mathrm{\Lambda }}_{K_n})=n!-\rho (n)$. On the same lines, (ii) is also proved. 

Proof.

1. Let $c:V({\mathrm{\Lambda }}_{K_n}^{\ast })\to \{c_1,c_2,\dots ,c_{(n-1)!}\}$ be a proper vertex coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ given as follows. First, assign the colors $c_1,c_2,\dots ,c_{(n-1)!}$ to the vertices $v_{\pi }\in V_1$, as it induces a clique of order $(n-1)!$ in ${\mathrm{\Lambda }}_{K_n}$. Following this, the vertices $v_{{\pi }^{\mathrm{\prime }}}\in V_i–\bigcup _{j=1}^{i-1}{V}_j$, for each $2\le i\le n-2$, in order, are colored based on its neighbours in $\bigcup _{j=1}^i{V}_j$ that are previously colored.

   If $v_{{\pi }^{\mathrm{\prime }}}\in V_i^1;2\le i\le n$, then we assign distinct colors to $v_{{\pi }^{\mathrm{\prime }}}$ such that $c(v_{{\pi }^{\mathrm{\prime }}})=c(v_{\pi })$, where $v_{\pi }\in V_1^1$, as these vertices are not adjacent in ${\mathrm{\Lambda }}_{K_n}$. If $v_{{\pi }^{\mathrm{\prime }}}\in V_j^k$; $k>1$, there exists at least one permutation $\pi \in S_n$ such that $\mathrm{f}\mathrm{i}\mathrm{x}(\pi )\cap \mathrm{f}\mathrm{i}\mathrm{x}({\pi }^{\mathrm{\prime }})=\mathrm{\varnothing }$, as $|\mathrm{f}\mathrm{i}\mathrm{x}(\pi )|\le n-2$, for any non-identity $\pi \in S_n$. If $|\mathrm{f}\mathrm{i}\mathrm{x}(\pi )|=n-2$, the existence of such a permutation is unique; otherwise, there exists a one-to-one correspondence between these permutations, as $\rho (n-k)$ is a constant. Therefore, we assign the color $c(v_{{\pi }^{\mathrm{\prime }}})=c(v_{\pi })$, where $v_{\pi }\in V_1$ and corresponds to $v_{{\pi }^{\mathrm{\prime }}}\in V_i;2\le i\le n$. Continuing the assignment for each $2\le i\le n$, in order, we obtain a Grundy coloring of ${\mathrm{\Lambda }}_{K_n}$ with $(n-1)!$ colors; establishing ${\chi }_{gr}({\mathrm{\Lambda }}_{K_n}^{\ast })\ge (n-1)!$. Coloring the $\rho (n)$ isolated vertices with the least value among the colors assigned to the vertices of ${\mathrm{\Lambda }}_{K_n}^{\ast }$, the Grundy coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ can be extended to a Grundy coloring of ${\mathrm{\Lambda }}_{K_n}$ with the same Grundy chromatic number. As we know that ${\chi }_{gr}(G)\le {\chi }_{ach}(G)$, for any graph $G$ (ref. [8]), the result follows from Theorem 2.1.

2. Consider the coloring $c:V({\overline{\mathrm{\Lambda }}}_{K_n})\to \{c_1,c_2,\dots ,c_{\rho (n)+n}\}$ such that the vertices of $V_i–\bigcup _{j=1}^{i-1}{V}_i$, for $1\le i\le n$, are assigned the colors $c_i$; $1\le i\le n$, for the corresponding $i$ values and the colors $c_i;n+1\le i\le n+\rho (n)$, are assigned to the $\rho (n)$ universal vertices. This is a Grundy coloring of ${\overline{\mathrm{\Lambda }}}_{K_n}$, as every vertex is colored by the smallest $c_j$ such that it has not occurred in its colored neighbors and ${\chi }_{gr}({\overline{\mathrm{\Lambda }}}_{K_n})\ge n+\rho (n)$. As the other inequality follows from Theorem 2.2, ${\chi }_{gr}({\overline{\mathrm{\Lambda }}}_{K_n})=n+\rho (n)$.

Proof. Every vertex in ${\mathrm{\Lambda }}_{K_n}^{\ast }$ is a part of a clique of order $(n-1)!$ and also each vertex of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ is adjacent to at least $(n-1)!-1$ vertices of a clique $V_i$, for some $1\le i\le n$. Hence, all the vertices of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ possess a rainbow neighbourhood or equivalently, are colorful. Hence, ${\chi }_f({\mathrm{\Lambda }}_{K_n}^{\ast })=(n-1)!$ and ${\psi }_f({\mathrm{\Lambda }}_{K_n}^{\ast })\ge (n-1)!$. The vertex connectivity of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ is $(n-1)!-1$, as the vertices in $V_i^1$; $1\le i\le n$, are adjacent only to the vertices of the corresponding $V_i$’s. Hence, ${\psi }_f({\mathrm{\Lambda }}_{K_n}^{\ast })$ cannot be greater than $(n-1)!$; thereby proving the result. 

Proof. The graph ${\mathrm{\Lambda }}_{K_n}$ cannot admit a fall coloring or $J$-coloring as it is disconnected and the isolated vertices cannot be colorful or have a rainbow neighbourhood. In the graph ${\overline{\mathrm{\Lambda }}}_{K_n}$, the vertex $v_{{\pi }_0}$ cannot be a colorful vertex because $v_{{\pi }_0}$ is adjacent only to the $\rho (n)$ universal vertices of ${\overline{\mathrm{\Lambda }}}_{K_n}$; whereas, $\omega ({\overline{\mathrm{\Lambda }}}_{K_n})=\chi ({\overline{\mathrm{\Lambda }}}_{K_n})=n+\rho (n)$. Hence the result. 

Proof. As every vertex of ${\mathrm{\Lambda }}_{K_n}$, except its isolated vertices, is colorful in ${\mathrm{\Lambda }}_{K_n}$, $r_{\chi }({\mathrm{\Lambda }}_{K_n}^{\ast })=r_{\chi }({\mathrm{\Lambda }}_{K_n})=n!-\rho (n)$. In any proper coloring of ${\overline{\mathrm{\Lambda }}}_{K_n}$, every vertex $v_{{\pi }_1}\in V_i^k$, for some $1\le k\le n$, is adjacent to at least the $\rho (n)$ universal vertices and the vertices $v_{{\pi }_2}\in V_j^1$, where $i\notin \mathrm{f}\mathrm{i}\mathrm{x}({\pi }_2)$. Since the vertices of $V_i^1;1\le i\le n$, induce a complete $n$-partite graph, it can be deduced that in the rainbow coloring of ${\overline{\mathrm{\Lambda }}}_{K_n}$, each $v_{\pi }\in V({\overline{\mathrm{\Lambda }}}_{K_n})$ is adjacent to the vertices of $\rho (n)+(n-k)$ color classes, where $k=|\mathrm{f}\mathrm{i}\mathrm{x}(\pi )|$. Hence the result. 

Proof. As a consequence of Theorem 2.7, we deduce that every vertex of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ is colorful. Hence, the proper vertex coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ by itself is a $b$-coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$. This coloring when extended to the isolated vertices by assigning one of the $(n-1)!$ colors used in any proper coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ does not alter the $b$-chromatic number of ${\mathrm{\Lambda }}_{K_n}$, as any $b$-coloring requires only one vertex of a color class to be colorful. Similarly, it can be observed that the chromatic coloring of ${\overline{\mathrm{\Lambda }}}_{K_n}$ is a $b$-coloring of ${\overline{\mathrm{\Lambda }}}_{K_n}$, as the $\rho (n)$ universal vertices and the vertices of $V_i^1$; $1\le i\le n$, are adjacent to each vertex of all color classes, except itself. Hence the result. 

Proof. As the diameter of the graph ${\mathrm{\Lambda }}_{K_n}^{\ast }$ is 2, any $L(2,1)$-coloring $c$ of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ assigns distinct colors to all the vertices. Hence, the number of colors required to color the vertices is $n!-\rho (n)$. As $0$ is also a color that can be assigned in an $L(2,1)$ coloring, and there exists a universal vertex $v_{{\pi }_0}$ in ${\mathrm{\Lambda }}_{K_n}^{\ast }$, ${\lambda }_L({\mathrm{\Lambda }}_{K_n}^{\ast })\ge n!-\rho (n)$. To prove that ${\lambda }_L({\mathrm{\Lambda }}_{K_n}^{\ast })=n!-\rho (n)$, we obtain an $L(2,1)$-coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ which assigns all colors $2,3,\dots ,n!-\rho (n)$ and 0, as follows.

First, assign the color 0 to $v_{{\pi }_0}$. Next, assign colors to the vertices of $V_i^k$; $\lfloor \frac{n}{2}\rfloor \le k\le n-2$, and $V_j^1$, for $1\le i\ne j\le n$, alternatively. As the vertices of $\bigcup _{i=1}^n[\bigcup _{k=\lfloor \frac{n}{2}\rfloor +1}^{n-2}{V}_i^k]$ induce a clique, these vertices cannot be assigned consecutive colors. Since every vertex of $V_i^k$; $\lfloor \frac{n}{2}\rfloor \le k\le n-2$, corresponding to a $k$-element fix is not adjacent to $(n-k)\rho (n-1)$ vertices of $V_i^1;1\le i\le n$, we assign consecutive colors from $2$ to $\sum _{k=\lfloor \frac{n}{2}\rfloor }^{n-2}(\genfrac{}{}{0ex}{}{n}{k})\rho (n-k)+1$ to the vertices of $V_i^k$; $\lfloor \frac{n}{2}\rfloor \le k\le n-2$, and $V_i^1;1\le i\le n$, by alternating between them. As $|\bigcup _{i=1}^n[\bigcup _{k=\lfloor \frac{n}{2}\rfloor }^{n-2}{V}_i^k]|=\sum _{k=\lfloor \frac{n}{2}\rfloor }^{n-2}(\genfrac{}{}{0ex}{}{n}{k})\rho (n-k)<n\rho (n-1)$, for all $n\ge 3$, there exists $n\rho (n-1)-\sum _{k=\lfloor \frac{n}{2}\rfloor }^{n-2}(\genfrac{}{}{0ex}{}{n}{k})\rho (n-k)$ vertices of $V_i^1;1\le i\le n$, left uncolored, at this stage.

The fixes of permutations in $R_1$ are either same or disjoint. Hence, the vertices of $V_i^1$; $1\le i\le n$, corresponding to these permutations with disjoint fixes are non-adjacent and we assign consecutive integers to these vertices by not assigning colors to two vertices of the same $V_i^1$, for any $1\le i\le n$, back to back. Hence, the value of the color given to the last vertex of ${\mathrm{\Lambda }}_{R_1};1\le i\le n$, is $n\rho (n-1)+\sum _{k=\lfloor \frac{n}{2}\rfloor }^{n-2}(\genfrac{}{}{0ex}{}{n}{k})\rho (n-k)+1$.

Following this, we color the vertices of $\bigcup _{i=1}^n{V}_i^k$; $2\le k\le \lfloor \frac{n}{2}\rfloor –1$, for which, first consider the $(\genfrac{}{}{0ex}{}{n}{k})$ distinct $k$-element fixes, for each $2\le k\le \lfloor \frac{n}{2}\rfloor –1$, and partition them into subsets of order $\lfloor \frac{n}{k}\rfloor$, such that each of them is a maximal subset of pairwise disjoint $k$-element fixes. Order the partite sets and the vertices in these partite sets, such that the first and the last element of a partite set has disjoint $k$-element fix with the last and the first element of the preceding and succeeding partite sets. Note that this ordering does not affect the nature of the partite set as the $\lfloor \frac{n}{k}\rfloor$ fixes in a partite set are mutually disjoint. Since each $R_k;2\le k\le \lfloor \frac{n}{2}\rfloor –1$, consists of $\rho (n-k)$ permutations with the same $k$-element fix, we extend the same partitioning and the ordering to all the $\rho (n-k)$ sets of $(\genfrac{}{}{0ex}{}{n}{k})$ distinct $k$-element fixes; thereby to the vertices corresponding to them, as well.

Assign colors to all vertices corresponding to the $\rho (n-k)$ sets of each of the partite set, from the first to the $\lceil \frac{k(\genfrac{}{}{0ex}{}{n}{k})}{n}\rceil$th, in order. In this assignment, all vertices can be assigned consecutive integers because each distinct $k$-element fix has $(\genfrac{}{}{0ex}{}{n-k}{k})$ disjoint $k$-element fixes, for all $2\le k\le \lfloor \frac{n}{2}\rfloor –1$, and $(\genfrac{}{}{0ex}{}{n-k}{k})>\lfloor \frac{n}{k}\rfloor +1$. Also, every vertex in $V_i^{k-1};1\le i\le n$, is not adjacent to least one vertex of $V_j^k;1\le i\ne j\le n$, for all $1\le k\le \lfloor \frac{n}{2}\rfloor -1$. Hence, all consecutive colors starting from $n\rho (n-1)+\sum _{k=\lfloor \frac{n}{2}\rfloor }^{n-2}(\genfrac{}{}{0ex}{}{n}{k})\rho (n-k)+2$, until $n\rho (n-1)+\sum _{k=\lfloor \frac{n}{2}\rfloor }^{n-2}(\genfrac{}{}{0ex}{}{n}{k})\rho (n-k)+1+\sum _{k=2}^{\lfloor \frac{n}{2}\rfloor -1}(\genfrac{}{}{0ex}{}{n}{k})\rho (n-k)$ are used to color the vertices; which on simplification yields ${\lambda }_L({\mathrm{\Lambda }}_{K_n}^{\ast })=n!-\rho (n)$. Any of the colors used in this $L(2,1)$-coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ can be given to the $\rho (n)$ isolated vertices of ${\mathrm{\Lambda }}_{K_n}$ to obtain an $L(2,1)$-coloring of ${\mathrm{\Lambda }}_{K_n}$, and hence yielding ${\lambda }_L({\mathrm{\Lambda }}_{K_n})=n!-\rho (n)$. 

Proof. The graph ${\overline{\mathrm{\Lambda }}}_{K_n}$ has $\rho (n)$ universal vertices to which we assign the colors $0,2,4,\dots ,$ $2(\rho (n)-1)$. Following this, assign the color $2\rho (n)$ to the vertex $v_{{\pi }_0}$. Next, we begin by assigning colors to the vertices of $V_i–\bigcup _{j=1}^{i-1};1\le i\le n$, such that the first vertex and the last vertex assigned color belongs to $V_i^1$ and $V_i\cap V_{i+1}$ (unless $i=n$) of the respective $V_i$’s. This assignment ensures that consecutive colors starting from $2\rho (n)+1$ to $n!+\rho (n)$ are given to these $n!-\rho (n)-1$ vertices, as each $V_i$ is an independent set and also, the first and last vertex in the sequence as per the requirement exists as $V_i$’s are not disjoint. As all possible consecutive labels are assigned to the non-universal vertices, and the universal vertices must be given non-consecutive colors in any $L(2,1)$-coloring of the graph ${\overline{\mathrm{\Lambda }}}_{K_n}$, we get ${\lambda }_L({\overline{\mathrm{\Lambda }}}_{K_n})=n!+\rho (n)$. 

Proof. The graph ${\mathrm{\Lambda }}_{K_n}^{\ast }$ has a universal vertex $v_{{\pi }_0}$ and hence in any equitable coloring of ${\mathrm{\Lambda }}_{K_n}^{\ast }$, each color class must be of cardinality either 1 or 2. Therefore, ${\chi }_e({\mathrm{\Lambda }}_{K_n}^{\ast })\ge \lceil \frac{n!-\rho (n)-1}{2}\rceil +1$. To prove the converse, we partition the $n!-\rho (n)-1$ non-universal vertices of ${\mathrm{\Lambda }}_{K_n}^{\ast }$ into independent sets of size 2 and claim that there can exist at most one singleton in such a partition.

For each $1\le k\le \lfloor \frac{n}{2}\rfloor$, consider the graph ${\mathrm{\Lambda }}_{R_k\cup R_{n-k}}$. As $|R_k|=(\genfrac{}{}{0ex}{}{n}{k})\rho (n-k)$ and $|R_{n-k}|=(\genfrac{}{}{0ex}{}{n}{k})\rho (k)$, $|R_k|\ge |R_{n-k}|$, for any $1\le k\le \lfloor \frac{n}{2}\rfloor$. Also, for each $1\le k\le \lfloor \frac{n}{2}\rfloor$, every vertex of ${\mathrm{\Lambda }}_{R_{n-k}}$ is not adjacent to exactly $k\rho (n-k)$ vertices of ${\mathrm{\Lambda }}_{R_k}$ and hence every vertex of ${\mathrm{\Lambda }}_{R_{n-k}}$ can be paired with a vertex of ${\mathrm{\Lambda }}_{R_k}$ such that they are not adjacent. Pairing the vertices of ${\mathrm{\Lambda }}_{R_k\cup R_{n-k}}$; $1\le k\le \lfloor \frac{n}{2}\rfloor$, in this manner can be viewed as an injective mapping $f:V({\mathrm{\Lambda }}_{R_{n-k}})\to V({\mathrm{\Lambda }}_{R_k})$, that gives $(\genfrac{}{}{0ex}{}{n}{k})\rho (k)$ independent sets $\{v,f(v)\}$ of cardinality 2. Therefore, at this stage, $(\genfrac{}{}{0ex}{}{n}{k})[\rho (n-k)-\rho (k)]$ vertices in each ${\mathrm{\Lambda }}_{R_k}$; $1\le k\le \lfloor \frac{n}{2}\rfloor$, are unpaired, implying that all the uncolored vertices are in ${\mathrm{\Lambda }}_{R_k}$; $1\le k\le \lfloor \frac{n}{2}\rfloor$.