• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

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

Vergara 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.0788 seconds