Resumen

Un arco de un grafo conectado es una coloración de aristas tal que para cualquier par de vértices distintos u y v de G hay al menos internamente caminos arco-disjuntos de colores. En este trabajo, aplicamos un Algoritmo Genético de Rango para buscar coloraciones arco de la familia de jaulas de Moore con cintura seis -jaulas. Encontramos que una cota superior en el número de colores necesarios para producir una coloración arco de 4 colores de una -jaula es 7, mejorando la actualmente conocida, que es 13. Se sabe que el cálculo del número mínimo de colores de una coloración arco es NP-Difícil y el Algoritmo Genético de Rango mostró un buen comportamiento al encontrar coloraciones arco con un pequeño número de colores.

• Materias:Ecuaciones elípticas Método asintótico Coeficiente variable Moléculas con fuerza Teoría de control óptimo
• Subjects:Elliptic equations Asymptotic method Variable coefficient Molecules with force Optimal control theory
• Palabras claves:Coloreo de aristas; Caminos arcoíris; Algoritmo Genético de Rango; Jaulas de Moore; Circunferencia seis; NP-Difícil
• Keywords:Edge coloring; Rainbow paths; Rank Genetic Algorithm; Moore cages; Girth six; NP-Hard