INVESTIGADORES
MAZZOLENI Maria Pia
congresos y reuniones científicas
Título:
Clique coloración de los grafos B1-EPG
Autor/es:
FLAVIA BONOMO; MARÍA PÍA MAZZOLENI; MAYA STEIN
Lugar:
Valparaiso
Reunión:
Congreso; Primer encuentro conjunto de la Sociedad de Matemática de Chile (SOMACHI) y la Unión Matemática Argentina (UMA), SUMA . 2016 (14 a 17 de diciembre del 2016, Valparaíso, Chile).; 2016
Institución organizadora:
Sociedad de Matemática de Chile (SOMACHI) y Unión Matemática Argentina (UMA)
Resumen:
Consideramos el problema de clique coloración, esto es, colorear los vértices de un grafo dado de modo que los cliques maximales de tamaño al menos dos no estén monocoloreados. Se sabe que los grafos de intervalos son 2-clique coloreables. Consideramos los grafos B1-EPG (grafos arista intersección de caminos en una grilla, donde cada camino tiene a lo sumo un giro). Se sabe que reconocer a los grafos B1-EPG es un problema NP-completo. También, el problema coloración y conjunto independiente máximo son NP-completos para los grafos B1-EPG. En este trabajo, probamos que los grafos B1-EPG son 4-clique coloreables. Más aún, dadauna representación B1-EPG de un grafo, damos un algoritmo de tiempo lineal que construyeuna 4-clique coloración de él.
