Electronic Journal of Graph Theory and Applications 14 .
, 71Ae82 New bounds on the connected-pseudoachromatic index of complete graphs Jorge Cervantes-Ojedaa .
Marya C.
Gymez-Fuentesa .
Christian Rubio-Montielb Department of Applied Mathematics and Systems.
Universidad Autynoma Metropolitana.
Unidad Cuajimalpa.
Mexico b Divisiyn de Matemyticas e Ingenierya.
FES Acatlyn.
Universidad Nacional Autynoma de Myxico.
CDMX - Mexico jcervantes@cua.
mx, mgomez@cua.
mx, christian.
rubio@acatlan.
Abstract 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.
Introduction The connected pseudoachromatic index of a complete graph, denoted by OcA (Kn ) .
r, in short.
Oc .
), 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 .
, .
, the exact determination of Oc .
remains a challenge in graph theory.
In this work, we focus on obtaining new bounds for Oc .
, 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.
New bounds connected-pseudoachromatic index Cervantes et al.
determining Oc .
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 (GA.
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 .
to theoretical challenges in discrete mathematics.
In particular, the Rank Genetic Algorithm (Rank GA) introduced in .
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 .
, .
Although previous research has successfully applied GAs to theoretical problems, such as graph coloring .
, .
and other combinatorial issues .
, 15, 14, .
, 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 OcA (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.
Problem Statement The maximum number of colors in a connected and complete coloring of a complete graph Kn of order n that can be achieved is called the connected-pseudoachromatic index and is denoted Oc .
There are certain values of n for which it is known, and for others, only the lower and upper bounds are known .
, .
The problem we address here, in particular, consists in improving the known bounds.
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).
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 .
shows an example of a complete edge-coloring of K4 , while Figure 1 .
shows an example of a non-complete coloring, since the color pair (AudottedAy.
AudashedA.
does not have a common vertex.
New bounds connected-pseudoachromatic index Cervantes et al.
Figure 1.
Edge-colorings in the complete graph K4 .
(Lef.
A complete coloring with 4 colors.
(Righ.
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.
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 OcA (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 Oc .
where n is the number of vertices in the complete graph Kn .
In .
it is shown that Oc .
can be bounded by analytical methods obtaining that Oc .
= o.
3/2 ).
Table 1 shows the known bounds of Oc .
, for complete and connected graphs of 2 O n O 31 vertices.
With the use of the computer, complete colorings can be achieved, and thus improve the lower bound of Oc .
Upper Lower Upper Lower Upper Lower Table 1.
Values for 2 O n O 7 and lower bounds for 8 O n O 12 given in .
The other values were given in .
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, schedul73 New bounds connected-pseudoachromatic index Cervantes et al.
ing, location and allocation, reliability design, and logistics .
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 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 .
The pseudocode for the Rank GA is shown in Algorithm 1 on page 75.
Adaptation of the Rank GA to the Edge Coloring Problem To address the problem of improving the bounds of the connected-pseudoachromatic index Oc .
of a complete graph Kn , we adapted the Rank GA.
This section describes the representation, fitness function, and mutation mechanism used in this adaptation.
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 .
umColors Oe .
, representing the available palette The length of the array equals the total number of edges in the complete graph, 2 .
This representation encodes a coloring of the graph that the algorithm evaluates and evolves toward better solutions.
Fitness Function The fitness function is calculated as:
fitness = Oe ( A weightPair.
Oe ( A weightColor.
Oe .
vg A weightAv.
Oe .
td A weightSt.
New bounds connected-pseudoachromatic index Cervantes et al.
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 .
, indices i OO .
, .
N Oe.
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 A Ia OI.
for each i:
ci = S.
Oe ri )SOe1 .
append UOci UU clones of Pi to P A .
Fractional rounding:
cycle i = 0, 1, .
until |P A | = N :
let fi = ci Oe UOci UU.
if rand()< fi then append Pi to P A .
P Ia P A.
STEP 3: Rank-based Recombination Sort P.
for pairs .
, i .
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.
max G)/ln(N Oe .
for each individual i in P set ri =i/N .
pi Ia pmax A riw .
for each gene gk of Pi if rand() < pi then mutate.
k , pi ) evaluate fitness of P.
end while STEP 5: Return the best individual A is the number of distinct colors used.
A is the number of unconnected pairs of color classes.
A is the number of disjoint color classes.
A avg is the average of all color codes in the genome of the individual.
A std is the sample standard deviation of the histogram of colors.
A 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.
New bounds connected-pseudoachromatic index Cervantes et al.
Results 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 Oc .
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.
Upper
Lower Improved Lower
Upper
Lower Improved Lower
Upper
Lower Improved Lower
7 10 11
16 17 18
40 45 51
26 27 28 29
22 23 24 25 26 27 28
74 78 82 86 90 94 98
46 50 52 54 55 59 62
Table 2.
Improved lower bounds with the Rank GA for Oc .
and n O 31.
Figure 2 shows the values in Table 2.
As can be seen, there are significant improvements to the lower bounds as n grows.
Values 2 4 6 8 1012141618202224262830 Upper Lower Lower Improved Figure 2.
Improved lower bounds with the Rank GA for Oc .
New bounds connected-pseudoachromatic index Cervantes et al.
On the upper bound Oo In .
it is shown that a complete graph p of n vertices accepts a coloring with ( n Oe .
/2 colors and that a coloring with .
Oe .
( n/2 1/16 1/.
colors or more cannot be complete and connected at the same time.
On the one hand, the asymptotic growth of Oc .
is o.
2 ), on the other hand, the coefficient of the main term of the lower bound is 21 , whereas it is Oo12 for the upper bound.
This gives a significant difference in the values in Table 1.
Theorem 5.
If n Ou 8, then an approximate upper bound is Oc .
O k OO Oo n.
Oe .
= n 2 O.
4n Oe 3 Oe 1 Proof.
Let n Ou 8 and C : E(Kn ) Ie .
, .
, .
a connected and complete edge-coloring of Kn with k = Oc .
Let x be the cardinality of the smallest chromatic class of C, that is, let x = min{|C Oe1 .
| : i OO .
, .
, .
Without loss of generality, suppose that x = |C Oe1 .
On the one hand.
C defines a partition of E(Kn ) and it follows that k O fn .
:= n.
Oe.
On the other hand.
C is connected, therefore.
C Oe1 .
is at least a tree subgraph.
The maximum number of edge-disjoint spanning trees in the subgraph H = Kx 1 , such that V (H) = V (C Oe1 .
), .
other chromatic is at most x2 , then the chromatic class x is incident to at most x2 Oe 1 = xOe1 In addition, there are .
Oe .
) edges that are incident to some vertex of C Oe1 .
at least once, but on average each class is x 1 incident to C Oe1 .
Since C is complete, the number of chromatic classes incident to C Oe1 .
containing no edge in H is at most .
Oe x Oe .
in average.
Hence, there are at most gn .
Oe 1 chromatic classes incident with some edge in C Oe1 .
where gn .
Oe 1 := .
Oe .
) xOe1 , according to the hypothesis of the average degree, i.
= n.
2 2x .
Oe x3 Oe 2x2 Oe 2x Oe 1 Then, we have Oc .
O k OO min.
, gn .
} and then Oc .
O k OO max .
, gn .
} with x OO N} .
As fn is a hyperbola and gn is a parabola there are two positive values x0 and x1 such that x0 < x1 , gn .
0 ) = fn .
0 ) and gn .
1 ) = fn .
1 ) for which fn .
O gn .
for x0 O x O x1 and gn .
< fn .
in any other case when x OO R .
Since fn .
0 ) > fn .
1 ), it follows that gn .
0 ) = fn .
0 ) = max .
, gn .
} with x OO R }, see Figure 3.
Equation fn .
0 ) = gn .
0 ) is reduced to n2 Oe .
20 2x0 .
n x30 2x20 2x0 1 = 0.
For the Oo positive solution, we obtain n = x20 x0 1 and then x0 = 4nOe3Oe1 taking the positive solution.
New bounds connected-pseudoachromatic index Cervantes et al.
Figure 3.
The functions gn and fn for some fixed value n.
, therefore we get fn .
0 ) = Oon.
Oe.
Since fn .
0 ) = n.
Oe.
4nOe3Oe1 n.
Oe .
Oc .
O k OO Oo 4n Oe 3 Oe 1 and the result is established.
Values Upper
2 4 6 8 1012141618202224262830
Approx Upper Lower Improved Lower Figure 4.
Improved bounds for Oc .
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 Oc .
for n = q 2 q 1 when q is an odd prime power according to the following New bounds connected-pseudoachromatic index Upper Approx Upper Lower Improved Lower Approx Upper Lower Improved Lower Approx Upper Lower Improved Lower Cervantes et al.
4 6 7 10 11
14 15 16 17 18
28 32 35 38 41
26 27 28 29
23 24 25 26 27 28
59 63 67 71 75 80
50 52 54 55 59 62
Table 3.
Improved bounds for Oc .
Theorem 5.
If q is an odd prime power and n = q 2 q 1 then n O Oc .
q Our approximation Oon.
Oe.
n is a good approximation because q is odd and 4nOe3Oe1 q n.
Oe.
n Oo Oo Oo 4nOe3Oe1 4.
Oe3Oe1 4q 4q 1Oe1 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 Oc .
, which represents the maximum number of colors in a connected and complete coloring of a complete graph Kn of order n.
The Rank GA demonstrated significant effectiveness in improving Oc .
bounds for complete graphs with connected classes.
Our paper enters into the set of problems with results for small n values such that: .
where it was proved that the well-known ErdoU-Faber-Lyvasz conjecture is true for n O 12.
where the extremal values of the C4 -free graphs are shown for n O 31.
While in .
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 Oc .
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 Oc .
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 However, their distribution does not align with the color patterns described in Theorem 5.
meaning that they lack a projective plane structure in their arrangement.
New bounds connected-pseudoachromatic index Cervantes et al.
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 K12 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://w.
com/scl/fo/ibudsyzgwj0gz8gzs8ifi/AEXSShINNc23KMsURaxS9 w4?rlkey=jsgye9loui8gapqnbm89c0csq&dl=0 New bounds connected-pseudoachromatic index Cervantes et al.
References