New bounds on the connected-pseudoachromatic index of complete graphs

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

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

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.5

References

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.

Y. Yuansheng and P. Rowlinson, On extremal graphs without four-cycles, Utilitas Math. 41 (1992), 204–210.

D. Romero and F. Alonso-Pecina, The Erd˝os-Faber-Lovász conjecture is true for n ≤ 12, Discrete Math. Algorithms Appl. 6(3) (2014), 1450039, 5.

M. Gen and L. Lin, Genetic algorithms and their applications, In: Springer handbook of engineering statistics. Springer, (2023), 635–674

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.

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.

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.

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.

M.G. Araujo-Pardo and C. Rubio-Montiel, Pseudoachromatic and connected pseudoachromatic indices of the complete graph, Discrete Appl. Math. 231 (2017), 60–66.

L. Abrams and Y. Berman, Connected pseudoachromatic index of complete graphs, Australas. J. Combin. 60 (2014), 314–324.

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.

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.

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.

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.

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.

C.C. Hsu and H.J. Cho, A genetic algorithm for the maximum edge-disjoint paths problem, Neurocomputing. 148 (2015), 17–22.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats