Defensa Tesis Doctorado Martín Safe

• Título de la tesis: "Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König"
• Directores: Flavia Bonomo y Guillermo Durán.
• Jurados:
  Dr. Andreas Brändstadt - University of Rostock, Alemania
  Dra. Maria Gutierrez - Universidad Nacional de La Plata, Argentina
  Dr. Fabio Protti - Universidade Federal Fluminense, Brasil
• Resumen:

Los grafos perfectos fueron definidos por Berge alrededor de 1960 mediante la igualdad de dos parámetros: el número clique y el número cromático. Estos grafos han recibido mucha atención desde entonces y el resultados más importante desde el punto de vista estructural referido a estos grafos es el Teorema Fuerte de los Grafos Perfectos que consisten en una caracterización de dichos grafos por subgrafos inducidos prohibidos. Esta caracterización fue conjeturada por Berge en los 60's y demostrada hace solo algunos años.

Berge definió en 1969 las matrices balanceadas como aquellas matrices de ceros y unos que no contienen ninguna submatriz cuadrada de orden impar con exactamente dos unos por fila y por columna. En 1970, Berge y Las Vergnas demostraron que los grafos balanceados, aquellos cuya cuya matriz de incidencia clique-vértice es balanceada, son perfectos.

En esta tesis se estudia en primer lugar el problema de caracterizar los grafos balanceados. A pesar de existir en la literatura una caracterización para estos grafos por subgrafos inducidos prohibidos, no se conoce ninguna caracterización por subgrafos inducidos prohibidos minimales. En esta tesis se dan algunos pasos en esta dirección, aportando caracterizaciones de los grafos balanceados por subgrafos inducidos prohibidos minimales para grafos que pertenecen a ciertas clases y se prueba que, dentro de algunas de esas clases, dichas caracterizaciones dan lugar a algoritmos lineales para el reconocimiento de los grafos balanceados.

En esta tesis se estudia también el problema de caracterizar los grafos clique-perfectos. Estos grafos, al igual que los perfectos, pueden definirse mediante la igualdad de dos parámetros: el número de independencia de cliques y el número transversal de cliques. Mientras que los grafos perfectos son aquellos en los que para todo subgrafo inducido las columnas de la matriz de incidencia clique-vértice tienen la propiedad de König, los clique-perfectos son precisamente aquellos en los que para todo subgrafo inducido las filas de la matriz de incidencia clique-vértice tienen la propiedad de K König. Actualmente no se conoce una caracterización completa por subgrafos inducidos prohibidos para los grafos clique-perfectos ni tampoco la complejidad de su reconocimiento, pero han aparecido caracterizaciones parciales restringiendo ambos problemas a grafos que pertenecen a ciertas clases de grafos. En esta tesis se caracterizan los grafos clique-perfectos por subgrafos inducidos prohibidos dentro de dos clases de grafos, lo que implica algoritmos de reconocimiento polinomiales para la clique-perfección dentro de dichas clases.

Un grafo tiene la propiedad de König si el mánimo número de vértices que intersecan todas las aristas iguala al máximo número de aristas que no comparten vértices, es decir, si sus aristas tienen la propiedad de König . Estos grafos fueron caracterizados por subgrafos prohibidos dentro de la clase de los grafos con un matching perfecto por Lovasz y este resultado fue recientemente extendido a una caracterización completa por obstrucciones prohibidas. En esta tesis se demuestra una versión más fuerte de este Último resultado estableciéndose una caracterización de los grafos con la propiedad de K König por subgrafos prohibidos y, como consecuencia, una caracterización de los grafos arista-perfectos por arista-subgrafos prohibidos.