Inmersiones de grafos completos en grafos densos y coloreamiento de vérticesReportar como inadecuado




Inmersiones de grafos completos en grafos densos y coloreamiento de vértices - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Profesor guía

Stein, Maya Jakobine; - Resumen

En la presente memoria se considera la relación entre coloreamiento de vértices y la nociónde inmersión. Específicamente, se estudia una conjetura propuesta por Abu-Khzam y Langston,la cual dice que el grafo completo de tamaño t está inmerso en todo grafo t-cromático.En primer lugar, se ven algunos resultados generales de inmersiones y se prueba que laconjetura se cumple para los grafos cuyo complemento no contiene ciclos inducidos de largocuatro y también para los grafos tales que todo conjunto de cinco vértices induce un subgrafocon al menos seis aristas. Luego, se da una breve mirada a una nueva relación definida, enun intento de generalizar la relación de inmersión.Finalmente, se estudia en detalle una clase especial de grafos, aquella de los grafos sinconjunto independiente de tamaño tres. Se presentan condiciones suficientes para que secumpla la conjetura de Abu-Khzam y Langston. Luego, se introduce una nueva conjetura,implicada por la conjetura de Abu-Khzam y Langston y se demuestra una versión un tantomás débil que ésta. Se prueba además, que ambas conjeturas son equivalentes. Por último,se exhiben una serie de propiedades que debería cumplir un contraejemplo mínimo, en casode existir alguno.Nota general

Ingeniera Civil Matemática



Autor: Vergara Soto, Sylvia Alejandra; -

Fuente: http://repositorio.uchile.cl/



DESCARGAR PDF




Documentos relacionados