Spelling suggestions: "subject:"coloreamiento dde vértices"" "subject:"coloreamiento dee vértices""
1 |
Inmersiones de grafos completos en grafos densos y coloreamiento de vérticesVergara Soto, Sylvia Alejandra January 2014 (has links)
Ingeniera Civil Matemática / 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.
|
Page generated in 0.0821 seconds