Resolución de problemas de gráficas usando el polinomio cromático.
Clave
CB003-23
Acuerdo
683.1.1.2.1.1
Fecha de inicio
19 de Abril de 2023
Fecha de Finalización
18 de Abril de 2026
Responsable
Participantes
Objetivos
General:
Obtener propiedades, diseñar algoritmos y métodos de solución eficientes para problemas de
gráficas utilizando el polinomio cromático.
Particulares
1. Diseñar modelos y algoritmos de solución de los problemas de coloración de gráficas,
mediante la utilización del polinomio cromático.
2. Implementar programas de cómputo que nos permitan, mediante el cálculo del polinomio
cromático de gráficas, obtener clasificaciones de gráficas en familias de gráficas
caracterizadas por cumplir propiedades y condiciones específicas. En particular, encontrar
las familias de gráficas que son χ-equivalentes, para un número fijo de vértices, así como las
gráficas que son χ-únicas y problemas derivados de dichos conceptos.
3. Formar recursos humanos, involucrando a alumnos de tesis y servicio social.
4. Proponer posibles aplicaciones a problemas que se pueden modelar mediante gráficas,
como son los problemas de asignación de horarios de ejecución de tareas, las interferencias
de distintas longitudes de ondas en estaciones de radio, el almacenamiento de productos
químicos, etc.