Inmersiones de grafos completos en grafos densos y coloreamiento de vértices

Abstract

En la presente memoria se considera la relación entre coloreamiento de vértices y la noción de 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 la conjetura se cumple para los grafos cuyo complemento no contiene ciclos inducidos de largo cuatro y también para los grafos tales que todo conjunto de cinco vértices induce un subgrafo con al menos seis aristas. Luego, se da una breve mirada a una nueva relación definida, en un intento de generalizar la relación de inmersión. Finalmente, se estudia en detalle una clase especial de grafos, aquella de los grafos sin conjunto independiente de tamaño tres. Se presentan condiciones suficientes para que se cumpla 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 tanto má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 caso de existir alguno.