In the literature of algebraic graph theory, an algebraic intersection graph called the invariant intersection graph of a graph has been constructed from the automorphism group of a graph. A specific class of these invariant intersection graphs was identified as the \(n\)-inordinate invariant intersection graphs, and its structural properties has been studied. In this article, we study the different types of proper vertex coloring schemes of these \(n\)-inordinate invariant intersection graphs and their complements, by obtaining the coloring pattern and the chromatic number associated.
For terminology in group theory, we refer to [7]. For basic definitions and results in graph theory, see [17] and for further concepts in algebraic graph theory, refer to [6]. We refer the reader to [9], for the fundamentals in combinatorics.
An automorphism of a graph \(G\) of order \(n\) is an isomorphism of \(G\) to itself. The automorphism group of \(G\), written as \(\mathop{\mathrm{Aut}}(G)\), is the set of all automorphisms defined on \(V(G)\) and is a subgroup of the symmetric group \(S_n\), which is the set of all permutations of a set with \(n\) elements. The fix of a permutation \(\pi \in S_n\) is the set of all elements whose image is invariant, and is given by \(\mathop{\mathrm{fix}}(\pi)=\{x \in S: \pi(x) = x\}\), where \(S\) is the set of \(n\) elements on which the permutations are defined.
Research in algebraic graph theory involves constructing graphs based on algebraic structures and investigating their properties (see [11,12]). In this direction, an algebraic intersection graph based on the automorphism group of a graph, called the invariant intersection graph \(\Lambda_G\) of a graph \(G\) was defined in [10] as the graph with the vertex set \(V(\Lambda_G) = \mathop{\mathrm{Aut}}(G)\), and any two distinct vertices \(v_{\pi_i}, v_{\pi_j} \in V(\Lambda_G)\) corresponding to the automorphisms \(\pi_i, \ \pi_j \in \mathop{\mathrm{Aut}}(G)\) are adjacent in \(\Lambda_G\) when \(\mathop{\mathrm{fix}}(\pi_i) \cap \mathop{\mathrm{fix}}(\pi_j) \neq \emptyset\).
In [13], the invariant intersection graphs of graphs with automorphism group as the symmetric group \(S_n\), were termed as the \(n\)-inordinate invariant intersection graphs and the structural properties of these graphs were studied extensively, along with the properties of their complements, called the \(n\)-inordinate invariant non-intersection graphs, where it was found that \(\Lambda_{K_n} \cong \Lambda^\ast_{K_n} \cup \rho(n)K_1\), where \(\rho(i)\); \(i \in \mathbb{N}\), is the number of derangements of \(i\) elements, and \(\Lambda^\ast_{K_n}\) is the non-trivial component of \(\Lambda_{K_n}\) having \(n!-\rho(n)\) vertices (see [13]).
An illustration of the \(n\)-inordinate invariant intersection graph is given in Figure 1. Throughout the study, we denote the identity permutation by \(\pi_0\) and the vertex corresponding to any permutation \(\pi \in \mathop{\mathrm{Aut}}(G)\) by \(v_{\pi} \in V(\Lambda_G)\).
In [13], it was proved that the graphs \(\Lambda_{K_n}\) and \(\overline{\Lambda}_{K_n}\) are weakly perfect, for all \(n\); that is, \(\chi(\Lambda_{K_n}) = \omega(\Lambda_{K_n}) = (n-1)!\) and \(\chi(\overline{\Lambda}_{K_n}) = \omega(\overline{\Lambda}_{K_n}) = n+\rho(n)\); whereas, are perfect only when \(n \leq 4\). This instills the curiosity to study different proper coloring schemes of these graphs, and to compare the chromatic numbers associated with these colorings with the clique number. Note that a graph \(G\) is weakly perfect if \(\chi(G) = \omega(G)\) and a graph \(G\) is perfect if \(\chi(H) = \omega(H)\), for all induced subgraphs \(H\) of \(G\) (see [17]).
Graph coloring is an assignment of colors to the vertices, edges or faces of a graph according to certain predefined rules. A proper coloring of a graph \(G\) is the assignment of colors to the entities of \(G\) such that no two adjacent entities receive the same color. Beginning with the chromatic coloring of a graph \(G\), several types of vertex colorings have been defined, based on the requirements of the assignment or scheduling problems that are to be represented as graph coloring problems.
The investigation of different coloring problems in algebraic graphs is an inquisitive topic of research as many algebraic graphs in the literature were constructed to satisfy certain coloring protocols (c.f. [3,4]). Therefore, in this section, we study different proper vertex coloring schemes of the \(n\)-inordinate invariant intersection graphs and the \(n\)-inordinate invariant non-intersection graphs, for which the following notions and notations defined in [13] are used.
The group \(S_n\) is partitioned into \(n\) sets such that, for \(1 \leq k \leq n\), \(R_k = \{\pi \in S_n : |\mathop{\mathrm{fix}}(\pi)|=k\}\) and for each \(1 \le k \le n\), the subgraph induced by \(R_k\) in \(\Lambda_{K_n}\) and \(\overline{\Lambda}_{K_n}\) are denoted by \(\Lambda_{R_k}\) and \(\overline{\Lambda}_{R_k}\), respectively. The vertex set of \(\Lambda_{K_n}\) is divided into \(n\) non-disjoint subsets \(V_i = \{v_\pi : i \in \mathop{\mathrm{fix}}(\pi)\}\); for \(1 \leq i \leq n\) and for each \(1 \le k \le n\), \(V_i^k = \{\pi \in V_i : \pi \in R_k \}; 1 \leq i \leq n\).
In this section, we discuss the coloring schemes for the graphs \(\Lambda_{K_n}\) and \(\overline{\Lambda}_{K_n}\), in which the assignment of colors to the vertices are defined based on the color-pairs that are induced by vertex pairs possessing some property. We begin the study by investigating the complete coloring of the graphs \(\Lambda^\ast_{K_n}\) and \(\overline{\Lambda}_{K_n}\).
A complete coloring of a graph \(G\) is a proper vertex coloring in which every pair of colors must appear on at least one pair of adjacent vertices and the maximum number of colors that can be used to obtain a complete coloring of \(G\) is the achromatic number of \(G\), denoted by \(\chi_{ach}(G)\) (c.f. [14]).
Proof. Note that \(\omega(\Lambda^\ast_{K_n}) = \chi(\Lambda^\ast_{K_n}) = (n-1)! \le \chi_{ach}(\Lambda^\ast_{K_n})\). If possible, assume that there exists a complete coloring \(c : V(\Lambda^\ast_{K_n}) \to \{c_1,c_2,\ldots, c_{(n-1)!+1}\}\) of \(\Lambda^\ast_{K_n}\). This implies that all \(\binom{(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(\Lambda^\ast_{K_n})\). Based on the adjacency pattern of vertices in the graph \(\Lambda_{K_n}\), any vertex in \(V^1_i\); \(1 \leq i \leq 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 \(\Lambda_{K_n}\) and hence \(v_{\pi_1} \notin V^1_i\); for any \(1 \leq i \leq n\).
On assigning \((n-1)!\) colors to the vertices of \(V_1\), the number of vertices in \(V_i – V_1\), for any \(2 \leq i \leq n\), that are to be colored, is less than \((n-1)!\). Also, the cardinality of the sets \(V_i – \bigcup\limits_{j=1}^{i-1}V_j\), for \(1 \leq i \leq 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\limits_{j=1}^{i-1}V_i\), for any \(1 \leq i \leq 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 \(\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}(\Lambda^\ast_{K_n}) = (n-1)!\). The same coloring can be extended to the graph \(\Lambda_{K_n}\), as the other components apart from \(\Lambda^\ast_{K_n}\) are trivial. ◻
Proof. As the graph \(\overline{\Lambda}_{K_n}\) has \(\omega(\overline{\Lambda}_{K_n}) = \chi(\overline{\Lambda}_{K_n}) = \rho(n)+n\), \(\chi_{ach}(\overline{\Lambda}_{K_n}) \geq \rho(n)+n\). Conversely, assume that \(\chi_{ach}(\overline{\Lambda}_{K_n}) = \rho(n)+n+1\) and let \(c\) be such a complete coloring of \(\overline{\Lambda}_{K_n}\) with \(\rho(n)+n+1\) colors, say \(c_1, c_2, \ldots, 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 \leq i \leq n\), to the vertices of \(V_i^1\), for the corresponding \(1 \le i \le n\), and the colors \(c_i; \, n+1 \leq i \leq \rho(n)+n\), to the \(\rho(n)\) universal vertices. For \(c\) to be a complete coloring of \(\overline{\Lambda}_{K_n}\), the color \(c_{\rho(n)+n+1}\) has to be assigned to any vertex \(v_{\pi} \in V_i^k\); \(1 \leq i \leq n\), and \(2 \leq k \leq n-2\), as \(v_{\pi_0}\) is adjacent to only the \(\rho(n)\) universal vertices and the subgraph of \(\overline{\Lambda}_{K_n}\) induced by \(\bigcup\limits_{i=1}^nV_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 |\mathop{\mathrm{fix}}(\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 \leq i \ne t_1 \ne t_2 \leq 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 \leq i \ne t_1 \ne t_2 \leq 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{\Lambda}_{K_n}) < n+\rho(n)+1\); completing the proof. ◻
A proper vertex coloring of a graph \(G\) is said to be an exact coloring of \(G\) if every pair of colors appear on exactly one pair of adjacent vertices and the maximum number of colors used to obtain an exact coloring of \(G\) is the exact chromatic number of \(G\) (see [5]).
Proof. As \(v_{\pi_0}\) is a universal vertex of the graph \(\Lambda^\ast_{K_n}\), we need \(n!-\rho(n)\) colors in order to obtain an exact coloring with respect to the color assigned to \(v_{\pi_0}\). For \(\Lambda^\ast_{K_n}\) to have exactly one edge having end vertices with all \(\binom{n!-\rho(n)-1}{2}\) pairs of colors, \(\Lambda^\ast_{K_n}\) must be a complete graph, which cannot happen for any \(n \geq 1\). Therefore, the graphs \(\Lambda^\ast_{K_n}\) and \(\Lambda_{K_n}\) do not admit an exact coloring. Using the similar argument based on the existence of \(\rho(n)\) universal vertices in \(\overline{\Lambda}_{K_n}\), it can be proved that \(\overline{\Lambda}_{K_n}\) also does not admit an exact coloring. ◻
A proper coloring in which every pair of colors appear on at most one pair of adjacent vertices of a graph \(G\) is called a harmonious coloring of \(G\) and the minimum number of colors used in a harmonious coloring of \(G\) is the harmonic chromatic number of \(G\), denoted by \(\chi_h(G)\) (c.f. [5]).
\(\chi_h(\Lambda^\ast_{K_n}) = \chi_h(\Lambda_{K_n}) = n!-\rho(n)\).
\(\chi_h(\overline{\Lambda}_{K_n}) = n!\).
Proof. The graph \(\Lambda^\ast_{K_n}\) contains a universal vertex \(v_{\pi_0}\), and hence every vertex in \(\Lambda^\ast_{K_n}\) must be given a unique color to obtain a harmonious coloring of \(\Lambda^\ast_{K_n}\). 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(\Lambda^\ast_{K_n}) = n!-\rho(n)\). Also, any harmonic coloring of \(\Lambda^\ast_{K_n}\) can be extended as the harmonic coloring of \(\Lambda_{K_n}\), by assigning any of the \(n!-\rho(n)\) colors used to color the vertices of \(\Lambda^\ast_{K_n}\) to the \(\rho(n)\) isolated vertices of \(\Lambda_{K_n}\), as the isolated vertices do not contribute to any edges in the graph. Therefore, \(\chi_h(\Lambda^\ast_{K_n}) = \chi_h(\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{\Lambda}_{K_n}\). ◻
Assigning colors to the vertices of a graph \(G\) such that no vertex \(v \in V(G)\) is adjacent to two vertices of the same color class is called an injective coloring of \(G\) and the minimum number of colors used to obtain such a coloring is called the injective chromatic number of \(G\), denoted by \(\chi_i(G)\) (ref. [15]). Note that an injective coloring of a graph is not usually not a proper coloring, but in the following result, we can observe that any injective coloring of the graphs \(\Lambda_{K_n}\) and \(\overline{\Lambda}_{K_n}\) turns out to be a proper coloring.
\(\chi_i(\Lambda^\ast_{K_n}) = \chi_i(\Lambda_{K_n}) = n!-\rho(n)\).
\(\chi_i(\overline{\Lambda}_{K_n}) = n!\).
Proof. According to the injective coloring protocol, if a vertex of \(\Lambda^\ast_{K_n}\) 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 \(\Lambda^\ast_{K_n}\). Any neighbour \(v_{\pi^\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^\prime}\) will have the same color. Therefore, any injective coloring of the graph \(\Lambda^\ast_{K_n}\) is a proper coloring of \(\Lambda^\ast_{K_n}\), which demands the assignment of unique colors to all its vertices. Any injective coloring of \(\Lambda^\ast_{K_n}\) is also an injective coloring of \(\Lambda_{K_n}\), as the \(\rho(n)\) trivial components do not have neighbours to alter the coloring protocol. Hence, \(\chi_i(\Lambda^\ast_{K_n}) = \chi_i(\Lambda_{K_n}) = n!-\rho(n)\). On the same lines, (ii) is also proved. ◻
In this section, we study the vertex colorings of the graphs \(\Lambda_{K_n}\), \(\Lambda^\ast_{K_n}\) and \(\overline{\Lambda}_{K_n}\), whose coloring protocols are given based on the neighbourhood of the vertices in the graph. Firstly, we investigate the Grundy coloring of these graphs, where a Grundy coloring of a graph \(G\) is a proper vertex coloring such that every vertex is colored by the smallest integer which has not appeared in any of its previously colored neighbours. The maximum number of colors that are used to obtain a Grundy coloring of \(G\) is the Grundy chromatic number of \(G\), \(\chi_{gr}(G)\) (ref. [14]).
\(\chi_{gr}(\Lambda^\ast_{K_n}) = \chi_{gr}(\Lambda_{K_n}) = (n-1)!\).
\(\chi_{gr}(\overline{\Lambda}_{K_n}) = n+\rho(n)\).
Proof.
Let \(c : V(\Lambda^\ast_{K_n}) \to \{c_1,c_2,\ldots, c_{(n-1)!}\}\) be a proper vertex coloring of \(\Lambda^\ast_{K_n}\) given as follows. First, assign the colors \(c_1,c_2,\ldots, c_{(n-1)!}\) to the vertices \(v_{\pi} \in V_1\), as it induces a clique of order \((n-1)!\) in \(\Lambda_{K_n}\). Following this, the vertices \(v_{\pi^{\prime}} \in V_i – \bigcup\limits_{j=1}^{i-1}V_j\), for each \(2 \leq i \leq n-2\), in order, are colored based on its neighbours in \(\bigcup\limits_{j=1}^{i}V_j\) that are previously colored.
If \(v_{\pi^\prime} \in V_i^1; \, 2 \le i \le n\), then we assign distinct colors to \(v_{\pi^{\prime}}\) such that \(c(v_{\pi^{\prime}}) = c(v_{\pi})\), where \(v_{\pi} \in V^1_1\), as these vertices are not adjacent in \(\Lambda_{K_n}\). If \(v_{\pi^{\prime}} \in V^k_j\); \(k >1\), there exists at least one permutation \(\pi \in S_n\) such that \(\mathop{\mathrm{fix}}(\pi) \cap \mathop{\mathrm{fix}}(\pi^{\prime}) = \emptyset\), as \(|\mathop{\mathrm{fix}}(\pi)| \leq n-2\), for any non-identity \(\pi \in S_n\). If \(|\mathop{\mathrm{fix}}(\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^{\prime}}) = c(v_{\pi})\), where \(v_{\pi} \in V_1\) and corresponds to \(v_{\pi^{\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 \(\Lambda_{K_n}\) with \((n-1)!\) colors; establishing \(\chi_{gr}(\Lambda^\ast_{K_n}) \geq (n-1)!\). Coloring the \(\rho(n)\) isolated vertices with the least value among the colors assigned to the vertices of \(\Lambda^\ast_{K_n}\), the Grundy coloring of \(\Lambda^\ast_{K_n}\) can be extended to a Grundy coloring of \(\Lambda_{K_n}\) with the same Grundy chromatic number. As we know that \(\chi_{gr}(G) \leq \chi_{ach}(G)\), for any graph \(G\) (ref. [8]), the result follows from Theorem 2.1.
Consider the coloring \(c : V(\overline{\Lambda}_{K_n}) \to \{c_1, c_2, \ldots, c_{\rho(n)+n}\}\) such that the vertices of \(V_i – \bigcup\limits_{j=1}^{i-1}V_i\), for \(1 \leq i \leq n\), are assigned the colors \(c_i\); \(1 \leq i \leq n\), for the corresponding \(i\) values and the colors \(c_i; \, n+1 \leq i \leq n+\rho(n)\), are assigned to the \(\rho(n)\) universal vertices. This is a Grundy coloring of \(\overline{\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{\Lambda}_{K_n}) \geq n+\rho(n)\). As the other inequality follows from Theorem 2.2, \(\chi_{gr}(\overline{\Lambda}_{K_n}) = n+\rho(n)\).
◻
A vertex \(v\) of a graph \(G\) is said to be colorful or is said to have a rainbow neighbourhood if \(v\) is adjacent to at least one vertex from every color class. The vertex coloring of \(G\) such that every vertex is colorful or possesses a rainbow neighbourhood is called a fall coloring or \(J\)-coloring. The minimum and maximum number of colors used to obtain a fall coloring of \(G\) are called the fall chromatic numbers of \(G\), denoted by \(\chi_f(G)\) and \(\psi_f(G)\), respectively (see [8]). The maximum number of colors that can be used to obtain a \(J\)-coloring of \(G\) is called the \(J\)-chromatic number of \(G\), denoted by \(\chi_j(G)\) (For details, refer to [16]). Note that the notions of fall and \(J\)-coloring of a graph \(G\) coincide, and hence \(\chi_j(G) = \psi_f(G)\).
Proof. Every vertex in \(\Lambda^\ast_{K_n}\) is a part of a clique of order \((n-1)!\) and also each vertex of \(\Lambda^\ast_{K_n}\) 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 \(\Lambda^\ast_{K_n}\) possess a rainbow neighbourhood or equivalently, are colorful. Hence, \(\chi_{f}(\Lambda^\ast_{K_n}) = (n-1)!\) and \(\psi_{f}(\Lambda^\ast_{K_n}) \geq (n-1)!\). The vertex connectivity of \(\Lambda^\ast_{K_n}\) is \((n-1)!-1\), as the vertices in \(V_i^1\); \(1 \leq i \leq n\), are adjacent only to the vertices of the corresponding \(V_i\)’s. Hence, \(\psi_{f}(\Lambda^\ast_{K_n})\) cannot be greater than \((n-1)!\); thereby proving the result. ◻
Proof. The graph \(\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{\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{\Lambda}_{K_n}\); whereas, \(\omega(\overline{\Lambda}_{K_n}) = \chi(\overline{\Lambda}_{K_n}) = n+\rho(n)\). Hence the result. ◻
The number of vertices of a graph \(G\) having rainbow neighbourhood is called the rainbow neighbourhood number of \(G\), denoted by \(r_{\chi}(G)\) (c.f. [16]). As a consequence of Theorem 2.7 and Proposition 2.8, the following corollary is obtained.
\(r_{\chi}(\Lambda^\ast_{K_n}) = r_{\chi}(\Lambda_{K_n}) = n!-\rho(n)\).
\(r_{\chi}(\overline{\Lambda}_{K_n}) = n\rho(n-1)+\rho(n)\).
Proof. As every vertex of \(\Lambda_{K_n}\), except its isolated vertices, is colorful in \(\Lambda_{K_n}\), \(r_{\chi}(\Lambda^\ast_{K_n}) = r_{\chi}(\Lambda_{K_n}) = n!-\rho(n)\). In any proper coloring of \(\overline{\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 \mathop{\mathrm{fix}}(\pi_2)\). Since the vertices of \(V_i^1; \, 1 \leq i \leq n\), induce a complete \(n\)-partite graph, it can be deduced that in the rainbow coloring of \(\overline{\Lambda}_{K_n}\), each \(v_\pi \in V(\overline{\Lambda}_{K_n})\) is adjacent to the vertices of \(\rho(n)+(n-k)\) color classes, where \(k = |\mathop{\mathrm{fix}}(\pi)|\). Hence the result. ◻
The minimum number of colors required to properly color the vertices of a graph \(G\) such that each vertex of \(G\) is adjacent to vertices of at least \(t-1\) different color classes is called the \(t\)-colorful chromatic number of \(G\), denoted by \(\chi_{tcol}(G)\), and such a coloring of \(G\) is called the \(t\)-colorful coloring of \(G\) (see [18]).
A vertex coloring of a graph \(G\) is said to be a \(b\)-coloring if at least one vertex of each color class is colorful. The minimum number of colors used in a \(b\)-coloring of \(G\) is called the \(b\)-chromatic number of \(G\), denoted by \(\chi_b(G)\) (ref. [8]).
\(\chi_b(\Lambda^\ast_{K_n}) = \chi_b(\Lambda_{K_n}) = \chi(\Lambda_{K_n})\).
\(\chi_b(\overline{\Lambda}_{K_n}) = \chi(\overline{\Lambda}_{K_n})\).
Proof. As a consequence of Theorem 2.7, we deduce that every vertex of \(\Lambda^\ast_{K_n}\) is colorful. Hence, the proper vertex coloring of \(\Lambda^\ast_{K_n}\) by itself is a \(b\)-coloring of \(\Lambda^\ast_{K_n}\). This coloring when extended to the isolated vertices by assigning one of the \((n-1)!\) colors used in any proper coloring of \(\Lambda^\ast_{K_n}\) does not alter the \(b\)-chromatic number of \(\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{\Lambda}_{K_n}\) is a \(b\)-coloring of \(\overline{\Lambda}_{K_n}\), as the \(\rho(n)\) universal vertices and the vertices of \(V_i^1\); \(1 \leq i \leq n\), are adjacent to each vertex of all color classes, except itself. Hence the result. ◻
The coloring protocols in which the assignment of colors between two vertices \(u,v\) in a graph \(G\) is based on the distance \(d(u,v) \geq 1\) are called distance related vertex colorings. In these colorings where the protocols involve only the assignment of distinct colors to vertices \(u,v\) at some distance \(d(u,v)\), and the parameter associated is the number of colors required, reduce to either the chromatic or the harmonious coloring of \(\Lambda^\ast_{K_n}\) and \(\overline{\Lambda}_{K_n}\), as these graphs have diameter 2. Hence, we study the distance related coloring schemes for these graphs, which does not coincide with any other proper coloring.
An \(L(2, 1)\)-coloring of a graph \(G\) is an assignment of non-negative integers as colors, to the vertices of \(G\) such that the colors assigned to adjacent vertices differ by at least 2, and the colors assigned to vertices at distance 2 differs by at least 1. For an \(L(2,1)\)-coloring \(c\) of \(G\), the \(c\)-cap of \(G\), \(\lambda_c(G) = \max\{c(v): v\in V(G) \}\) and \(L\)-cap of \(G\), \(\lambda_{L}(G) = \min\{\lambda_c(G)\}\), where the minimum is taken over all possible \(L(2, 1)\)-colorings \(c\) of \(G\) (c.f. [2]).
Proof. As the diameter of the graph \(\Lambda^\ast_{K_n}\) is 2, any \(L(2, 1)\)-coloring \(c\) of \(\Lambda^\ast_{K_n}\) 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 \(\Lambda^\ast_{K_n}\), \(\lambda_{L}(\Lambda^\ast_{K_n}) \geq n!-\rho(n)\). To prove that \(\lambda_{L}(\Lambda^\ast_{K_n}) = n!-\rho(n)\), we obtain an \(L(2,1)\)-coloring of \(\Lambda^\ast_{K_n}\) which assigns all colors \(2, 3, \ldots, 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 \neq j \le n\), alternatively. As the vertices of \(\bigcup\limits_{i=1}^{n}\Big[\bigcup\limits_{k=\lfloor \frac{n}{2} \rfloor+1}^{n-2}V_i^{k}\Big]\) 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\limits_{k=\lfloor \frac{n}{2} \rfloor}^{n-2}\binom{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 \(\Big|\bigcup\limits_{i=1}^{n}\Big[\bigcup\limits_{k=\lfloor \frac{n}{2} \rfloor }^{n-2}V_i^{k}\Big]\Big|= \sum\limits_{k=\lfloor \frac{n}{2} \rfloor}^{n-2}\binom{n}{k}\rho(n-k) < n\rho(n-1)\), for all \(n \geq 3\), there exists \(n\rho(n-1)-\sum\limits_{k=\lfloor \frac{n}{2} \rfloor}^{n-2}\binom{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 \(\Lambda_{R_1}; \, 1 \le i \le n\), is \(n\rho(n-1)+\sum\limits_{k=\lfloor \frac{n}{2} \rfloor}^{n-2}\binom{n}{k}\rho(n-k)+1\).
Following this, we color the vertices of \(\bigcup\limits_{i=1}^nV_i^k\); \(2 \le k \le \lfloor\frac{n}{2}\rfloor – 1\), for which, first consider the \(\binom{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 \(\binom{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 \(\Big\lceil \frac{k\binom{n}{k}}{n} \Big\rceil\)th, in order. In this assignment, all vertices can be assigned consecutive integers because each distinct \(k\)-element fix has \(\binom{n-k}{k}\) disjoint \(k\)-element fixes, for all \(2 \le k \le \lfloor\frac{n}{2}\rfloor – 1\), and \(\binom{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 \neq 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\limits_{k=\lfloor \frac{n}{2} \rfloor}^{n-2}\binom{n}{k}\rho(n-k)+2\), until \(n\rho(n-1)+\sum\limits_{k=\lfloor \frac{n}{2} \rfloor}^{n-2}\binom{n}{k}\rho(n-k)+1+\sum\limits_{k=2}^{\lfloor \frac{n}{2} \rfloor-1}\binom{n}{k}\rho(n-k)\) are used to color the vertices; which on simplification yields \(\lambda_{L}(\Lambda^\ast_{K_n}) = n!-\rho(n)\). Any of the colors used in this \(L(2,1)\)-coloring of \(\Lambda^\ast_{K_n}\) can be given to the \(\rho(n)\) isolated vertices of \(\Lambda_{K_n}\) to obtain an \(L(2,1)\)-coloring of \(\Lambda_{K_n}\), and hence yielding \(\lambda_{L}(\Lambda_{K_n}) = n!-\rho(n)\). ◻
Proof. The graph \(\overline{\Lambda}_{K_n}\) has \(\rho(n)\) universal vertices to which we assign the colors \(0, 2, 4, \ldots,\) \(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\limits_{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{\Lambda}_{K_n}\), we get \(\lambda_{L}(\overline{\Lambda}_{K_n}) = n!+\rho(n)\). ◻
A proper vertex coloring of a graph \(G\) such that two colors \(i\) and \(j\) are assigned to \(u, v \in V(G)\) when \(d(u, v) + |i-j| \geq 1 + r\), for some fixed \(r \in \mathbb{N}\); not greater than the diameter of \(G\) is called \(r\)-radio coloring of \(G\). The value of a radio coloring \(c\) of \(G\), \(rc_r(c) = \max\{c(v): v\in V(G) \}\) and the \(r\)-radio chromatic number of \(G\), \(rc_r(G) = \min\{rc_r(c)\}\), where the minimum is taken over all possible \(r\)-radio colorings \(c\) of \(G\) (c.f. [2]). When \(r\) is the diameter of \(G\) and \(r\) is one less than the diameter of \(G\), the colorings are called the radio and antipodal colorings of \(G\), and the corresponding chromatic numbers are called the radio and antipodal numbers of \(G\), denoted by \(rn(G)\) and \(an(G)\), respectively. Since the diameter of \(\Lambda^\ast_{K_n}\) and \(\overline{\Lambda}_{K_n}\) is 2, we obtain the following result.
\(rn(\Lambda^\ast_{K_n}) = \lambda_L(\Lambda^\ast_{K_n})\).
\(an(\Lambda^\ast_{K_n}) = \chi(\Lambda^\ast_{K_n})\).
\(rn(\overline{\Lambda}_{K_n}) = \lambda_L(\overline{\Lambda}_{K_n})\).
\(an(\overline{\Lambda}_{K_n}) = \chi(\overline{\Lambda}_{K_n})\).
A proper vertex coloring of a graph \(G\) in which the cardinality of the color classes differ by at most 1 is called an equitable coloring of \(G\). The minimum number of colors used to obtain an equitable coloring of \(G\) is the equitable chromatic number, denoted by \(\chi_e(G)\) (ref. [14]). In this section, we obtain the equitable coloring pattern and determine the equitable chromatic number of the graphs \(\Lambda^\ast_{K_n}\), \(\Lambda_{K_n}\) and \(\overline{\Lambda}_{K_n}\).
Proof. The graph \(\Lambda^\ast_{K_n}\) has a universal vertex \(v_{\pi_0}\) and hence in any equitable coloring of \(\Lambda^\ast_{K_n}\), each color class must be of cardinality either 1 or 2. Therefore, \(\chi_e(\Lambda^\ast_{K_n}) \geq \lceil \frac{n!-\rho(n)-1}{2}\rceil+1\). To prove the converse, we partition the \(n!-\rho(n)-1\) non-universal vertices of \(\Lambda^\ast_{K_n}\) into independent sets of size 2 and claim that there can exist at most one singleton in such a partition.
For each \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\), consider the graph \(\Lambda_{R_k \cup R_{n-k}}\). As \(|R_k| = \binom{n}{k}\rho(n-k)\) and \(|R_{n-k}| = \binom{n}{k}\rho(k)\), \(|R_k| \geq |R_{n-k}|\), for any \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\). Also, for each \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\), every vertex of \(\Lambda_{R_{n-k}}\) is not adjacent to exactly \(k\rho(n-k)\) vertices of \(\Lambda_{R_k}\) and hence every vertex of \(\Lambda_{R_{n-k}}\) can be paired with a vertex of \(\Lambda_{R_k}\) such that they are not adjacent. Pairing the vertices of \(\Lambda_{R_k \cup R_{n-k}}\); \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\), in this manner can be viewed as an injective mapping \(f : V(\Lambda_{R_{n-k}}) \to V(\Lambda_{R_k})\), that gives \(\binom{n}{k}\rho(k)\) independent sets \(\{v, f(v)\}\) of cardinality 2. Therefore, at this stage, \(\binom{n}{k}[\rho(n-k)-\rho(k)]\) vertices in each \(\Lambda_{R_k}\); \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\), are unpaired, implying that all the uncolored vertices are in \(\Lambda_{R_k}\); \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\).
Consider the \(\binom{n}{k}[\rho(n-k)-\rho(k)]\) vertices in each \(\Lambda_{R_k}\); \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\). As each \(\Lambda_{R_k}\); \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\), is not a clique, there exists at least one vertex of \(\Lambda_{R_k}\) to which a vertex of \(\Lambda_{R_k}\) is not adjacent to or equivalently, for every \(k\)-element fix, there exists at least one other \(k\)-element fix, such that they are disjoint. Hence, these vertices corresponding to these disjoint fixes of each \(\Lambda_{R_k}\) can be paired.
If \(\binom{n}{k}\) is even, then the vertices of that \(\Lambda_{R_k}\) can be paired within themselves. If \(\binom{n}{k}\) is odd, for some \(1 \leq k \leq \lfloor\frac{n}{2}\rfloor\), then after pairing the first set of \(\binom{n}{k}-1\) vertices that correspond to distinct \(k\)-element fixes, we pair the left out vertex to a vertex in the second set among the \(\rho(n-k) – \rho(k)\) sets of \(\binom{n}{k}\) vertices that correspond to distinct \(k\)-element fixes. As there exists vertices of at least 2 distinct \(k\)-element fixes to which a vertex that corresponds to a permutation fixing \(k\) elements is not adjacent to, for any \(1 \le k < \lfloor\frac{n}{2} \rfloor\), such pairing is possible in any \(\Lambda_{R_k}\); \(1 \le k < \lfloor\frac{n}{2} \rfloor\). If \(\rho(n-k)\) is even and \(\binom{n}{k}\) is odd, at this point, all vertices are paired. Otherwise, when both \(\rho(n-k)\) and \(\binom{n}{k}\) are odd, there will exist exactly one unpaired vertex from each \(\Lambda_{R_k}\); \(1 \le k < \lfloor\frac{n}{2} \rfloor\), of this kind. If exactly one vertex is left unpaired among all \(\Lambda_{R_k}\)’s, we are done.
If there exists more than one unpaired vertex at this stage, we pair these unpaired vertices based on their non-adjacency, which in turn leaves us with at most one singleton, yielding the required number of pairs. The pairing of these unpaired vertices can be done because \(|\mathop{\mathrm{fix}}(\pi)| \leq n-2\) for all non-identity permutations of \(S_n\) and the unpaired vertices of the graph \(\Lambda_{R_k}\) can be permuted with the vertices of \(\Lambda_{R_k}\) in such a way that the graph induced by these left out vertices from each \(\Lambda_{R_k}\) of this kind has at least one unique vertex to which every unpaired vertex is not adjacent to, owing to the structure of \(S_n\). Hence, \(\chi_e(\Lambda^\ast_{K_n}) = \lceil \frac{n!-\rho(n)-1}{2}\rceil+1\). ◻
Proof. The graph \(\overline{\Lambda}_{K_n}\) has \(\rho(n)\) universal vertices. Therefore, in any equitable coloring of \(\overline{\Lambda}_{K_n}\), the colors are assigned to the vertices of \(\overline{\Lambda}_{K_n}\) such that each color class is of cardinality either 1 or 2, implying that \(\chi_e(\overline{\Lambda}_{K_n}) \geq \lceil \frac{n!-\rho(n)}{2}\rceil+\rho(n)\). To prove that \(\chi_e(\overline{\Lambda}_{K_n}) = \lceil \frac{n!-\rho(n)}{2}\rceil+\rho(n)\), we partition the \(n!-\rho(n)\) vertices of \(\overline{\Lambda}_{K_n}\) into independent sets of order 1 or 2, by pairing them, and claim that there can exist at most one singleton in such a partition.
In \(\overline{\Lambda}_{K_n}\), the graph \(\bigcup\limits_{k= \lfloor\frac{n}{2}\rfloor+1}^{n}\overline{\Lambda}_{R_k}\) is an empty graph. Hence, these vertices in \(\bigcup\limits_{k= \lfloor\frac{n}{2}\rfloor+1}^{n}\overline{\Lambda}_{R_k}\) can be paired in any manner. If \(\sum\limits_{k= \lfloor\frac{n}{2}\rfloor+1}^{n}\binom{n}{k}\rho(n-k)\) is even, we obtain no unpaired vertices; otherwise, pair the left out vertex with \(v_{\pi_0}\). Note that \(v_{\pi_0}\) can be paired with any of the non-universal vertices of \(\overline{\Lambda}_{K_n}\). Based on the number of vertices in each \(\overline{\Lambda}_{R_k}\); \(1 \leq k \leq \lfloor \frac{n}{2}\rfloor\), we pair them as follows.
Consider \(\overline{\Lambda}_{R_k}\), for \(1 \leq k \leq \lfloor \frac{n}{2}\rfloor\). Every vertex of \(\overline{\Lambda}_{R_k}\) is not adjacent to at least \(\rho(n-k)-1\) vertices in \(\overline{\Lambda}_{R_k}\), as they correspond to permutations having the same \(k\)-element fix. If both \(\rho(n-k)\) and \(\binom{n}{k}\) are even, then two vertices corresponding to the same \(k\)-element fix can be paired and we obtain \(\frac{\rho(n-k)}{2}\binom{n}{k}\) pairs of vertices in each of the corresponding \(\overline{\Lambda}_{R_k}\)’s. If \(\rho(n-k)\) is odd and \(\binom{n}{k}\) is even, then two vertices corresponding to the same \(k\)-element fix can be paired until we obtain \(\frac{\rho(n-k)-1}{2}\binom{n}{k}\) pairs of vertices of in the corresponding \(\overline{\Lambda}_{R_k}\) and one set among the \(\rho(n-k)\) sets of \(\binom{n}{k}\) vertices are paired within themselves. For any \(2 \le k \le \lfloor \frac{n}{2}\rfloor\), this pairing is possible because there exists at least two \(k\)-element fixes that are not disjoint and hence the vertices corresponding to them can be paired.
If both \(\rho(n-k)\) and \(\binom{n}{k}\) are odd, pair the \(\rho(n-k)(\binom{n}{k}-1)\) vertices as mentioned above. Hence, we obtain exactly one unpaired vertex here. If this is the only unpaired vertex among all \(\overline{\Lambda}_{R_k}\)’s, we either pair it with \(v_{\pi_0}\) or it becomes the only singleton; proving the result. If there is one such unpaired vertex from more than one \(\overline{\Lambda}_{R_k}; \, 1 \le k \le \lfloor \frac{n}{2}\rfloor\), we pair the vertices in that set of unpaired vertices if each vertex of this set has at least one unique vertex to which it is not adjacent to. Otherwise, the unpaired vertex of \(\overline{\Lambda}_{R_k}\) which does not have such a unique vertex to which it is not adjacent to, is permuted with the other paired vertices of \(\overline{\Lambda}_{R_k}\) in such a way that the unpaired vertex obtained after permuting has a unique vertex in the set of other unpaired vertices, to which it is not adjacent to. This swapping of vertices among the vertices of \(\overline{\Lambda}_{R_k}\), for each \(k\) is possible owing to the structure of \(S_n\). Therefore, we obtain at most one unpaired vertex at the end of the process, yielding the required value of the equitable chromatic number. ◻
Note that, unlike the other coloring schemes, the equitable coloring of \(\Lambda^\ast_{K_n}\) cannot be extended to the graph \(\Lambda_{K_n}\) because \(\Lambda_{K_n}\) has \(\rho(n)\) isolated vertices, to which any color can be assigned. As \(\omega(\Lambda^\ast_{K_n}) = \omega(\Lambda_{K_n})= (n-1)!\), we know that \(\chi_e(\Lambda_{K_n}) \geq (n-1)!\). Also, \(\alpha(\Lambda^\ast_{K_n}) = n\). This implies that ideally, the \(n!\) vertices of \(\Lambda_{K_n}\) must be distributed equally to the \((n-1)!\) color classes; that is, \(n\) per color class, which will be an equitable coloring with the minimum number of colors. With respect to the assignment of colors to the vertices of \(\Lambda^\ast_{K_n}\) in a chromatic coloring, the color class of \(v_{\pi_0}\) is of cardinality 1 and only for the \(\rho(n-1)\) color classes assigned to the vertices of \(V_i^1\), we can ensure cardinality \(n\). Therefore, for this assignment of colors to the vertices of \(\Lambda^\ast_{K_n}\) to be an equitable assignment of colors to the vertices of \(\Lambda_{K_n}\), the \(\rho(n)\) isolated vertices are distributed to each of the \((n-1)! – \rho(n-1)\) color classes, such that all the color classes have the same cardinality \(n\) or differ at most by 1.
The number of isolated vertices to be added to each of the color class which has less than \(n\) vertices cannot be precisely mentioned as it depends on the assignment. Also, as the value of \(\rho(n)\) is computed based on the integer partitioning of \(n\) and the permutations corresponding to these partitioning that does not fix \((n-k)\) elements, it grows rapidly and at this stage of the study, a pattern for \(\rho(n)\) values also does not exists, owing to its dependency on the theory of integer partitioning, which by itself is an unsolved problem (For details, refer to [1]). Hence, the possibility of assignment, though ideally must hold, (holds till \(n=10\)), could not be proved with the expected rigour. Therefore, we conclude the section by posing the following conjecture.
In this article, we examined various proper vertex coloring schemes on the \(n\)-inordinate invariant intersection graphs and their complements. It is interesting to see that almost all the chromatic numbers associated with various coloring patterns are equal to the chromatic number or the order of the graphs. This increases the interest to realise some coloring in the literature for which the assignment is different, prompting a wide scope to investigate other coloring schemes like improper vertex colorings and domination related vertex colorings, edge colorings and so on of the \(n\)-inordinate invariant intersection graphs and the \(n\)-inordinate invariant non-intersection graphs.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.