Programa

Unidad 1: Un repaso histórico. Grafos Eulerianos. Cliques y conjuntos independientes. Planaridad. Coloreo y sus variantes. Grafos perfectos.

Unidad 2: Grafos de intersección. Definición. Caracterizaciones de diferentes clases: cordales, de intervalos, de línea, clique, arco-circulares, circulares, de permutación. Su uso en algoritmos eficientes para problemas clásicos en dichas clases.

Unidad 3: Clases de grafos definidas por subgrafos o patrones prohibidos. Familias finitas e infinitas. Ejemplos de grafos que pueden ser definidos de esta manera: cografos, línea, split, de comparabilidad, cordales, de intervalos. Teoremas de descomposición de cografos y grafos claw-free. Su uso en algoritmos eficientes para problemas clásicos en dichas clases.

Bibliografía básica:

Brandstadt A., Bang Le V. and Spinrad J., Graph classes: A survey, SIAM, 1999.

Diestel R., Graph Theory, Springer-Verlag, 2000.

Golumbic M.C., Algorithmic graph theory and perfect graphs, Annals of Discrete Mathematics, Vol 57, 2004.

McKee T. and McMorris F., Topics in intersection graph theory, SIAM, 1999.