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.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/131290 |
| Date | January 2014 |
| Creators | Vergara Soto, Sylvia Alejandra |
| Contributors | Stein, Maya Jakobine, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Matemática, Rapaport Zimermann, Iván, Soto San Martín, José |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Atribución-NoComercial-SinDerivadas 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0018 seconds