New bounds on the connected-pseudoachromatic index of complete graphs

Jorge Cervantes-Ojeda^a , María C. Gómez-Fuentes^a , Christian Rubio-Montiel^b

Universidad Autónoma Metropolitana, Unidad Cuajimalpa, Mexico

jcervantes@cua.uam.mx, mgomez@cua.uam.mx, christian.rubio@acatlan.unam.mx

We improve several previously known bounds of the connected-pseudoachromatic index of complete graphs. We apply a Rank Genetic Algorithm to find experimental solutions above the known lower bounds and then we obtain an approximation of the upper bound to verify and compare to the empirically obtained results.

Keywords: Hadwiger number, edge-coloring, connected classes, Genetic algorithm, rank GA

Mathematics Subject Classification : 05C15, 05C85

DOI: 10.5614/ejgta.2026.14.1.5

1. Introduction

The connected pseudoachromatic index of a complete graph, denoted by ψ ′ c (Kn) (or, in short, ψc(n)), is a combinatorial parameter of theoretical interest due to its intrinsic complexity and the limited number of known exact results for complete graphs with connected classes. Although bounds have been obtained using analytical methods [9, 10], the exact determination of ψc(n) remains a challenge in graph theory.

In this work, we focus on obtaining new bounds for ψc(n), which not only improve upon previous bounds but also offer a novel perspective on this challenging problem. The difficulty in

Received: 12 February 2025, Revised: 6 November 2025, Accepted: 16 December 2025.

^aDepartment of Applied Mathematics and Systems,

^bDivisión de Matemáticas e Ingeniería, FES Acatlán, Universidad Nacional Autónoma de México, CDMX - Mexico

determining ψc(n) lies in the combinatorial complexity inherent in the connectivity and distribution of classes within the complete graph, which has motivated the search for both analytical and computational techniques to address this challenge.

Within the broad spectrum of computational methods, Genetic Algorithms (GAs) have emerged as powerful tools that combine analytical and computational approaches to solve complex optimization problems in diverse fields, ranging from industrial applications in transportation and manufacturing [4] to theoretical challenges in discrete mathematics. In particular, the Rank Genetic Algorithm (Rank GA) introduced in [5] stands out for incorporating genetic operators that facilitate a balance between local search and global search. This characteristic has enabled it to achieve promising results in solving combinatorial optimization problems [6, 7].

Although previous research has successfully applied GAs to theoretical problems, such as graph coloring [11, 12] and other combinatorial issues [13, 15, 14, 16], in this study, we emphasize the promising synergy between evolutionary techniques and theoretical analysis as a means to further refine the bounds. Thus, our proposal is a hybrid strategy that combines analytical and computational approaches and seeks to deepen the characterization of the connected pseudoachromatic index in complete graphs.

In summary, this article presents new bounds for ψ ′ c (Kn), contributing to theoretical advances in graph theory and opening new ways for applying evolutionary techniques to highly complex combinatorial problems.

The structure of this paper is as follows. In Section 2 we state the problem and include the necessary definitions to understand it. In Section 3 we describe the Rank GA, Section 4 shows how the Rank GA was adapted to the edge-coloring problem, and in Section 5 we present the obtained results. Finally, Section 6 contains the conclusions.

2. Problem Statement

The maximum number of colors in a connected and complete coloring of a complete graph Kⁿ of order n that can be achieved is called the connected-pseudoachromatic index and is denoted ψc(n). There are certain values of n for which it is known, and for others, only the lower and upper bounds are known [10, 9]. The problem we address here, in particular, consists in improving the known bounds.

2.1. Edge-Colorings of a Complete Graph

A graph is defined as a set of vertices V and a set of edges E, and is denoted by G = (V, E). It is important to note that, in a graph, there cannot be repeated edges or edges connecting a vertex to itself, since these conditions would violate the definition of a graph. A complete graph is a graph in which each pair of vertices is connected by an edge.

A complete edge-coloring in a complete graph is an assignment of colors to edges such that, for every pair of colors, there is at least a common vertex. Figure 1 (left) shows an example of a complete edge-coloring of K4, while Figure 1 (right) shows an example of a non-complete coloring, since the color pair ("dotted", "dashed") does not have a common vertex.

Figure 1. Edge-colorings in the complete graph K4. (Left) A complete coloring with 4 colors. (Right) A non-complete coloring with 5 colors.

A chromatic class is the set of all edges of a colored graph with the same color. The induced subgraph of a chromatic class X is formed by those edges in the chromatic class X and all the vertices connected to those edges.

A graph is connected when there is at least one path between each pair of its vertices. A chromatic class is connected if its induced subgraph is connected. Each chromatic class in Figure 1 is connected. A coloring is connected if all its chromatic classes are connected chromatic classes.

The connected-pseudoachromatic index ψ ′ c (G) of a graph G is the maximum number of colors k for which a connected and complete edge-coloring exists in the graph G using k colors, when G is connected; otherwise, it is defined as the maximum index over its connected components. When we color vertices and each chromatic class is connected, the parameter is also known as the Hadwiger number of G from the perspective of minor graphs.

When a graph is complete, the connected-pseudoachromatic index is denoted by ψc(n) where n is the number of vertices in the complete graph Kn.

In [9] it is shown that ψc(n) can be bounded by analytical methods obtaining that ψc(n) = Θ(n 3/2 ). Table 1 shows the known bounds of ψc(n), for complete and connected graphs of 2 ≤ n ≤ 31 vertices. With the use of the computer, complete colorings can be achieved, and thus improve the lower bound of ψc(n).

Table 1. Values for 2 ≤ n ≤ 7 and lower bounds for 8 ≤ n ≤ 12 given in [10]. The other values were given in [9].

3. Description of the Rank GA

Genetic algorithms draw inspiration from the genetic evolution process observed in living organisms, addressing challenges in combinatorial optimization, network design, routing, schedul-

ing, location and allocation, reliability design, and logistics [4]. Leveraging this evolutionary concept, we use the Rank GA to solve the problem described in Section 2, making use of its ability to escape local optima and refine solutions. The Rank GA operates by evaluating and ranking the population before applying each genetic operator. This ranking ensures that the corresponding genetic operator is uniquely applied to each individual based on their position in the ordered population. This approach enhances the ability to search for optimal solutions and to improve the bounds obtained thus far.

Individuals recombine with others of similar rank, so if one individual is fit due to possessing certain beneficial genes and another individual is fit for having different advantageous genes, their recombination can yield individuals that combine both sets of genes. If two individuals are unfit, they are likely to be quite different because there are numerous ways to be unfit. When recombined, it is highly probable that the offspring will also be distinct, exploring areas distant from the parents and, thereby, increasing the likelihood of escaping local optima. The fittest individuals tend to propagate their genes more within the population than the less fit ones. This allows the concentration of the population around the best individual, guiding the population towards the best individuals by exploiting their genes more.

In summary, with the Rank GA the worst individuals are dedicated to exploration making possible to escape from the local optima and, at the same time, the best individuals perform local search exploiting their genes to refine the best solution obtained so far. Therefore, the Rank GA is particularly suitable for optimization problems where finding a global optimum is challenging due to complex search spaces, as in the problem that we address in this study. For a more detailed explanation of this algorithm we refer the reader to [8].

The pseudocode for the Rank GA is shown in Algorithm 1 on page 75.

4. Adaptation of the Rank GA to the Edge Coloring Problem

To address the problem of improving the bounds of the connected-pseudoachromatic index ψc(n) of a complete graph Kn, we adapted the Rank GA. This section describes the representation, fitness function, and mutation mechanism used in this adaptation.

4.1. Representation

Each solution, or individual, in the genetic algorithm is represented as an array of integers, where each integer corresponds to the color assigned to a specific edge in Kn. The range of possible values for each gene is from 0 to (numColors − 1), representing the available palette of colors. The length of the array equals the total number of edges in the complete graph, n 2 . This representation encodes a coloring of the graph that the algorithm evaluates and evolves toward better solutions.

4.2. Fitness Function

The fitness function is calculated as:

fitness = α − (β · weightPairs) − (γ · weightColors) − (avg · weightAvg) − (std · weightStd),
where:

Algorithm 1 Rank Genetic Algorithm (Rank GA)

Parameters: population size N, selection pressure S=3, genome size G, maximal mutation rate pmax
Rank convention: population sorted by fitness (desc), indices i ∈ {0, . . . , N−1}
STEP 1: Initialization Initialize P with N individuals; evaluate fitness.
while stopping criterion not met do
   STEP 2: Rank-based Selection
   Sort P;
   for each individual i set ri=i/N.
   Integer cloning:
   P
     ′← ∅;
   for each i:
      ci = S(1 − ri)
                     S−1
                         ;
      append ⌊ci⌋ clones of Pi
                               to P
                                    ′
                                     .
   Fractional rounding:
   cycle i= 0, 1, . . . until |P′
                              |=N:
      let fi =ci − ⌊ci⌋;
      if rand()<fi
                     then append Pi
                                     to P
                                         ′
                                          ;
   P ←P′
           .
   STEP 3: Rank-based Recombination
   Sort P;
   for pairs (i, i+1) with i = 0, 2, . . . :
      recombine Pi with Pi+1 with replacement
   evaluate fitness of P.
   STEP 4: Mutation by Rank
   Sort P;
   set w = ln(pmaxG)/ln(N − 1);
   for each individual i in P
      set ri=i/N; pi ← pmax · r
                                 w
                                 i
                                   ;
      for each gene gk of Pi
        if rand() < pi
                        then mutate(gk, pi)
   evaluate fitness of P.
end while
STEP 5: Return the best individual

• α is the number of distinct colors used.
• β is the number of unconnected pairs of color classes.
• γ is the number of disjoint color classes.
• avg is the average of all color codes in the genome of the individual.
• std is the sample standard deviation of the histogram of colors.
• weightPairs, weightColors, weightStd, and weightAvg are weighting factors.

This function penalizes the average color code to favor low code values; it has no impact on the results and is included only to allow a better analysis of the solutions.

5. Results

5.1. On the lower bound

Table 2 presents the improved lower bounds obtained through the Rank GA for various values of n. The known upper bounds for ψc(n) are also shown for reference in Table 2. By comparing the improved lower bounds with the existing lower and upper bounds, we observed significant reductions in the gap between them.

Table 2. Improved lower bounds with the Rank GA for ψc(n) and n ≤ 31.

Figure 2 shows the values in Table 2. As can be seen, there are significant improvements to the lower bounds as n grows.

Figure 2. Improved lower bounds with the Rank GA for ψc(n).

5.2. On the upper bound

In [9] it is shown that a complete graph of n vertices accepts a coloring with \((\sqrt{n-1})^3/2\) colors and that a coloring with \((n-1)(\sqrt{n/2+1/16}+1/4)\) colors or more cannot be complete and connected at the same time.

On the one hand, the asymptotic growth of \(\psi_c(n)\) is \(\Theta(n^{\frac{3}{2}})\), on the other hand, the coefficient of the main term of the lower bound is \(\frac{1}{2}\), whereas it is \(\frac{1}{\sqrt{2}}\) for the upper bound. This gives a significant difference in the values in Table 1.

Theorem 5.1. If \(n \ge 8\), then an approximate upper bound is

\[\psi_c(n) \le k \approx \frac{n(n-1)}{\sqrt{4n-3}-1} = \frac{1}{2}n^{\frac{3}{2}} + O(n).\]

Proof. Let \(n \geq 8\) and \(\varsigma \colon E(K_n) \to \{1, \dots, k\}\) a connected and complete edge-coloring of \(K_n\) with \(k = \psi_c(n)\) colors.

Let x be the cardinality of the smallest chromatic class of \(\varsigma\), that is, let \(x = min\{|\varsigma^{-1}(i)| : i \in \{1, ..., k\}\}\). Without loss of generality, suppose that \(x = |\varsigma^{-1}(k)|\).

On the one hand, \(\varsigma\) defines a partition of \(E(K_n)\) and it follows that \(k \leq f_n(x) := n(n-1)/(2x)\).

On the other hand, \(\varsigma\) is connected, therefore, \(\varsigma^{-1}(k)\) is at least a tree subgraph. The maximum number of edge-disjoint spanning trees in the subgraph \(H=K_{x+1}\), such that \(V(H)=V(\varsigma^{-1}(k))\), is at most \(\frac{\binom{x+1}{2}}{x}\), then the chromatic class x is incident to at most \(\frac{\binom{x+1}{2}}{x}-1=\frac{x-1}{2}\) other chromatic classes. In addition, there are (x+1)(n-(x+1)) edges that are incident to some vertex of \(\varsigma^{-1}(k)\) at least once, but on average each class is \(\frac{2x}{x+1}\) incident to \(\varsigma^{-1}(k)\). Since \(\varsigma\) is complete, the number of chromatic classes incident to \(\varsigma^{-1}(k)\) containing no edge in H is at most

\[\frac{(x+1)(n-x-1)}{2x/(x+1)} \tag{5.1}\]

in average.

Hence, there are at most \(g_n(x)-1\) chromatic classes incident with some edge in \(\varsigma^{-1}(k)\) where \(g_n(x)-1:=\frac{(x+1)^2}{2x}(n-(x+1))+\frac{x-1}{2}\), according to the hypothesis of the average degree, i.e.

\[g_n(x) = \frac{n(x^2 + 2x + 1) - x^3 - 2x^2 - 2x - 1}{2x}.\]

Then, we have \(\psi_c(n) \leq k \approx \min\{f_n(x), g_n(x)\}\) and then

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

As \(f_n\) is a hyperbola and \(g_n\) is a parabola there are two positive values \(x_0\) and \(x_1\) such that \(x_0 < x_1\), \(g_n(x_0) = f_n(x_0)\) and \(g_n(x_1) = f_n(x_1)\) for which \(f_n(x) \le g_n(x)\) for \(x_0 \le x \le x_1\) and \(g_n(x) < f_n(x)\) in any other case when \(x \in \mathbb{R}^+\). Since \(f_n(x_0) > f_n(x_1)\), it follows that \(g_n(x_0) = f_n(x_0) = \max{\{\min\{f_n(x), g_n(x)\} \text{ with } x \in \mathbb{R}^+\}}\), see Figure 3.

Equation \(f_n(x_0) = g_n(x_0)\) is reduced to \(n^2 - (x_0^2 + 2x_0 + 2)n + x_0^3 + 2x_0^2 + 2x_0 + 1 = 0\). For the positive solution, we obtain \(n = x_0^2 + x_0 + 1\) and then \(x_0 = \frac{\sqrt{4n-3}-1}{2}\) taking the positive solution.

Figure 3. The functions \(g_n\) and \(f_n\) for some fixed value n.

Since \[f_n(x_0)=\frac{n(n-1)}{2x_0}\] we get \(f_n(x_0)=\frac{n(n-1)}{\sqrt{4n-3}-1}\), therefore \[\psi_c(n)\leq k\approx\frac{n(n-1)}{\sqrt{4n-3}-1}\]

and the result is established.

Figure 4. Improved bounds for \(\psi_c(n)\).

As we can see in Table 3, for the values of n=13 and 31 there are good approximations, which is due to the existence of the finite projective plane of odd order q=3 and 5, which gives a lower bound of \(\psi_c(n)\) for \(n=q^2+q+1\) when q is an odd prime power according to the following result.

Table 3. Improved bounds for \(\psi_c(n)\).

Theorem 5.2. [9] If q is an odd prime power and \(n = q^2 + q + 1\) then

\[\left\lceil \frac{q}{2} \right\rceil n \le \psi_c(n).\]

Our approximation \(\frac{n(n-1)}{\sqrt{4n-3}-1}\) implies that \(\lceil \frac{q}{2} \rceil n\) is a good approximation because q is odd and then

then \[\frac{n(n-1)}{\sqrt{4n-3}-1} = \frac{n(q^2+q)}{\sqrt{4(q^2+q+1)-3}-1} = \frac{q(q+1)n}{\sqrt{4q^2+4q+1}-1} = \frac{q(q+1)n}{2q} = \frac{(q+1)}{2}n = \left\lceil \frac{q}{2} \right\rceil n.\]

6. Conclusions

The problem at hand involves improving, by adapting a genetic algorithm called Rank GA, the known bounds of the connected-pseudoachromatic index for the complete graph of order n, denoted by \(\psi_c(n)\), which represents the maximum number of colors in a connected and complete coloring of a complete graph \(K_n\) of order n. The Rank GA demonstrated significant effectiveness in improving \(\psi_c(n)\) bounds for complete graphs with connected classes. Our paper enters into the set of problems with results for small n values such that: [3] where it was proved that the well-known Erdő-Faber-Lóvasz conjecture is true for \(n \leq 12\); [2] where the extremal values of the \(C_4\)-free graphs are shown for \(n \leq 31\). While in [1] all the Steiner Triplets Systems of order 19 were found.

The algorithm was able to find the solutions due to its balance in exploring the solution space and exploiting promising solutions. The improved bounds of \(\psi_c(n)\) obtained by the Rank GA were validated against an analytical approximation, confirming their validity. The success of the Rank GA in enhancing the bounds of \(\psi_c(n)\) may significantly contribute to theoretical advancements in Chromatic Graph Theory. Upon examination of the resulting colorings, it is observed that the sizes of the chromatic classes vary, with most sizes equal to the minimum size stipulated by Theorem 5.1. However, their distribution does not align with the color patterns described in Theorem 5.2, meaning that they lack a projective plane structure in their arrangement.

Beyond the specific problem of graph coloring, the findings underscore the interdisciplinary impact of utilizing genetic algorithms in theoretical mathematical research.

Finally, Figure 5 presents a sample solution with n = 12 and 21 colors. Additional examples and a Python-based visualizer can be downloaded from 1 . The visualizer allows users to toggle the visualization of each color class to analyze solutions.

Figure 5. Graph visualizer interface showing a connected complete edge-coloring of K¹² with 21 colors.

Acknowledgement

The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.

The authors have no relevant financial or non-financial interests to disclose.

The authors wish to thank the anonymous referees of this paper for their suggestions and remarks.

¹https://www.dropbox.com/scl/fo/ibudsyzgwj0gz8gzs8ifi/AEXSShINNc23KMsURaxS9 w4?rlkey=jsgye9loui8gapqnbm89c0csq&dl=0

References

• [1] C.J. Colbourn, A.D. Forbes, M.J. Grannell, T.S. Griggs, P. Kaski, P.R.J. Östergård, D.A. Pike, and O. Pottonen, Properties of the Steiner triple systems of order 19, Electron. J. Combin. 17(1) (2010), Research Paper 98, 30.
• [2] Y. Yuansheng and P. Rowlinson, On extremal graphs without four-cycles, Utilitas Math. 41 (1992), 204–210.
• [3] D. Romero and F. Alonso-Pecina, The Erdos-Faber-Lovász conjecture is true for ˝ n ≤ 12, Discrete Math. Algorithms Appl. 6(3) (2014), 1450039, 5.
• [4] M. Gen and L. Lin, Genetic algorithms and their applications, In: Springer handbook of engineering statistics. Springer, (2023), 635–674.
• [5] J. Cervantes and C.R. Stephens, Rank based variation operators for genetic algorithms, In: Proceedings of the 10th annual conference on Genetic and evolutionary computation. (2008), 905–912.
• [6] J. Cervantes-Ojeda, M. Gómez-Fuentes, D. González-Moreno, and M. Olsen, Rainbow connectivity using a rank genetic algorithm: Moore cages with girth six, J. Appl. Math. (2019), Art. ID 4073905, 7.
• [7] J.C. García-Altamirano, M. Olsen, and J. Cervantes-Ojeda, How to construct the symmetric cycle of length 5 using Hajós construction with an adapted rank genetic algorithm, Discrete Math. Theor. Comput. Sci. 25(1) (2023), Paper No. 3, 11.
• [8] J. Cervantes-Ojeda, M. Gómez-Fuentes, and J.A. Fresán-Figueroa, Applying Genetic Algorithms to Validate a Conjecture in Graph Theory: The Minimum Dominating Set Problem, In: Mexican International Conference on Artificial Intelligence. (2023), 271–282.
• [9] M.G. Araujo-Pardo and C. Rubio-Montiel, Pseudoachromatic and connectedpseudoachromatic indices of the complete graph, Discrete Appl. Math. 231 (2017), 60–66.
• [10] L. Abrams and Y. Berman, Connected pseudoachromatic index of complete graphs, Australas. J. Combin. 60 (2014), 314–324.
• [11] S.M. Douiri and S. Elbernoussi, Solving the graph coloring problem via hybrid genetic algorithms, Journal of King Saud University–Engineering Sciences. 27(1) (2015), 114–118.
• [12] T. Mostafaie, F.M. Khiyabani, and N.J. Navimipour, A systematic study on meta-heuristic approaches for solving the graph coloring problem, Computers & Operations Research. 120 (2020), 104850.
• [13] O. Cosma, P.C. Pop, and I. Zelina, An effective genetic algorithm for solving the clustered shortest-path tree problem, IEEE Access. 9 (2021), 15570–15591.

• [14] H. Xu, Y. Ge, and G. Zhang, Genetic algorithm for Traveling Salesman Problem, In: 5th International Conference on Computational Intelligence and Intelligent Systems. (2022), 33– 40.
• [15] D.T. Long, An enhanced genetic algorithm based courses timetabling method for maximal enrollments using maximum matching on bipartite graphs, Vietnam Journal of Science and Technology. 57(16) (2019), 734–748.
• [16] C.C. Hsu and H.J. Cho, A genetic algorithm for the maximum edge-disjoint paths problem, Neurocomputing. 148 (2015), 17–22.