Dos problemas de particiones matriciales en gráficas cordales

Ponente(s): Juan Carlos García Altamirano, Dr. César Hernández Cruz

Una gráfica simple no dirigida G = (V,E) es una pareja ordenada, donde V es un conjunto no vacío de vértices y E un conjunto de aristas que consiste de parejas no ordenadas de elementos de V. La cantidad de vértices y la cantidad de aristas en G son llamados orden y tamaño de G respectivamente. Una gráfica F = (V’,E’) es llamada subgráfica de G si V’ ⊆ V y E’ ⊆ E . Decimos que G contiene a F ó F está contenida en G y lo denotamos F ⊆ G. Un ciclo de tres o más vértices es una gráfica simple cuyos vértices pueden ser arreglados en secuencia cíclica de tal forma que dos vértices son adyacentes si y sólo si son consecutivos en dicha secuencia. El tamaño de un ciclo es el número de aristas del mismo. Una cuerda de un ciclo C en una gráfica G es una arista, fuera de las aristas de C, cuyos extremos son vértices no consecutivos de C. Una gráfica simple no dirigida G es cordal si cualquier ciclo de tamaño mayor que tres tiene un cuerda. Sea M una matriz simétrica de m por m sobre 0, 1, ∗. Una M-partición de una gráfica G = (V,E) es una partición V1, V2, ..., Vm de V tal que dos vértices distintos en partes (posiblemente iguales) vi y vj son adyacentes si M(i,j) = 1 y no adyacentes si M(i,j) = 0; la entrada M(i,j) = ∗ significa que no hay restricción. Ya que admitimos que i = j, un conjunto Vi es independiente si M(i,i) = 0, y un clan si M(i,i) = 1. Permitiremos que Vi = ∅, por ello no consideraremos las matrices donde M(i,i) = ∗. Este concepto generaliza los problemas de coloración y homomorfismos. Decimos que G es una obstrucción mínima de M si G que no admite una M-partición, pero cada subgráfica inducida propia de G sí admite una M -partición. En el contexto de gráficas cordales, Tomás Feder, Pavol Hell y Shekoofeh Nekooei Rizi, obtuvieron el siguiente resultado: “si M es una matriz de tamaño m < 4, entonces M tienen una cantidad finita de obstrucciones mínimas, excepto para dos matrices de 3 por 3, M1 y M2 las cuales tienen un cantidad infinita de obstrucciones mínimas”. Nuestro trabajo consiste en exponer explícitamente todas las obstrucciones mínimas (a pesar de ser infinitas) de M1 y M2. Más aún, en el proceso de la demostración desarrollamos herramientas para esbozar un algoritmo que mejora los resultados desarrolladas con anterioridad.