I Simposio de Postgrado 2023. Ingeniería, ciencias e innovación

MÓDULO_ 07 Matemáticas aplicadas y Modelación matemática 136 COMPLEJIDAD DE LISTA 3-COLOREO PARA CLASES DE GRAFOS CON ESTRUCTURAS PROHIBIDAS Y CON RESTRICCIONES DE DIÁMETRO 1 Departamento de Ingeniería Matemática, Universidad de Chile. *Email: axelkolmsatek@gmail.com Axel Kolm 1* , Maya Stein 1 RESUMEN Dado un grafo G= (V,E), el problema de lista 3-coloreo consiste en asignar un color a cada vértice de un grafo tal que todo par de vértices adyacentes poseen distinto color usando solo 3 colores. Este es un problema NP-completo en el caso general. Este es un problema con varias aplicaciones en modelamiento matemático y en teoría de la computación. El objetivo es determinar la com- plejidad del problema para clases especiales de grafos donde se restringen ciertas propiedades del grafo. En particular, determi- namos la complejidad para los grafos con K l 1,r prohibido y con diámetro d. Esta clase se caracteriza por estar compuesta de gra- fos donde todos los vértices se encuentran cercanos bajo una no- ción de distancia y no poseen ciertas estructuras dentro del grafo. Dividimos esta clase en 2 subclases, demostrando que en el caso donde d > 2l+1, el problema tiene complejidad polinomial y en el caso d < 2l+1 es NP-completo. Esto clasifica todos los casos excep- to por d=2l+1 donde la complejidad aun no ha sido determinada.