MATE 8001. Teoría de Grafos I

Código MATE 8001
Titulo Teoría de Grafos I
Creditos 3
Horas 3 por semana
Prerrequisitos MATE 5CCC Teoría de Grafos
Descripción Repaso de teoría de grafos elemental. Árboles. Teorema del árbol de matrices. Enumeración de árboles expansivos en un grafo. Descomposiciones de grafos. Conexidad y k-conexidad de grafos. Caminos disjuntos y conexidad de grafos. Teoremas de Menger y Whitney. Montaje y desmontaje de grafos para grafos 3-conexos y quasi 4-conexos. Varios problemas de Euler. Ciclos de Hamiltonian. La k-clausura de un grafo. Teorema de Bondy-Chvátal. Ciclos largos en un grafo. Teorema de Dirac. Factores. Pareos máximos y perfectos. Teoremas de Tutte y de Edmonds-Gallai. Teorema de dualidad de Berge-Tutte. Grafos perfectos. Teorema de Lovász. Coloreo de aristas. Teorema de Vizing. Conjuntos independientes. Coloreo de vértices. Teorema de Brook. Inserción de grafos en el plano. Criterios de planaridad de Kuratowski, Whitney, MacLane y Kelmans. Teoremas de cinco y cuatro colores para grafos planares. Acerca de la Hamiltoniedad de grafos planares.
Información adicional