Sobre la complejidad de reconocer una subfamilia de gráficas (2,1)-polares

Ponente(s): Ollin Tonatiuh Cortéz Gottwald, César Hernández Cruz

Es posible reconocer si una gráfica es escindible o bipartita en tiempo lineal, mientras que reconocer si una gráfica es k-coloreable es un problema NP-completo para k al menos 3. Las gráficas (k,l)-polares, gráficas que admiten ser partidas en una gráfica k coloreable y en l clanes, son una generalización natural de las gráficas escindibles. Para cualesquiera enteros k y l, es posible reconocer si una gráfica es (k,l)-polar en tiempo polinomial. Podemos representar los problemas de partición anteriores mediante el uso de patrones, matrices cuadradas con entradas {0,1,*} que nos dan restricciones de adyacencia entre las partes de la gráfica. Que una gráfica admita ser partida bajo cierto patrón es una propiedad hereditaria de gráficas, lo que nos permite caracterizarla mediante obstrucciones mínimas, subgráficas inducidas mínimas por contención que no tienen dicha propiedad. Estas obstrucciones mínimas son útiles como no-certificados al diseñar algoritmos de reconocimiento. Nos centramos en el estudio de una subfamilia de gráficas (2,1)-polares y expondremos los avances realizados en el estudio de la complejidad de determinar si una gráfica admite ser partida por el patrón que describe a dicha subfamilia.