Algoritmos de lista 3-coloreo para grafos con diámetro acotado y subgrafos inducidos prohibidos
Tesis

Access note
Acceso abierto
Publication date
2024Metadata
Show full item record
Cómo citar
Stein, Maya
Cómo citar
Algoritmos de lista 3-coloreo para grafos con diámetro acotado y subgrafos inducidos prohibidos
Author
Professor Advisor
Abstract
En esta tesis realizamos un breve resumen de la literatura en la complejidad del problema de coloreo para clases de grafos definidas por grafos inducidos prohibidos. Nos centramos en explorar los casos donde agregamos una restricción adicional que es acotar el diámetro del grafo.
Demostramos que 3-lista coloreo puede ser resuelto en tiempo polinomial para grafos $K^{\ell}_{1,r}$-libres con diámetro $d \geq 2\ell +2$ y NP-completo con $d<2\ell +1$ para todo $r\geq 1, \ell \geq 1$. Adicionalmente, demostramos que lista 3-coloreo puede ser resuelto en tiempo quasi-polinomial para grafos $(C_{8},C_{3})$-libres con diámetro 2. Finalmente, definimos un nuevo tipo de grafo $C^{*}_{8}$ como un $C_{8}$ con una 3-cuerda adicional y demostramos que lista 3-coloreo se puede resolver en tiempo polinomial para grafos $(C^{*}_{8},C_{8},C_{3})$-libres con diámetro 2.
xmlui.dri2xhtml.METS-1.0.item-notadetesis.item
Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas Memoria para optar al título de Ingeniero Civil Matemático
Patrocinador
Este trabajo ha sido parcialmente financiado por:
FONDECYT Regular 1221905
Identifier
URI: https://repositorio.uchile.cl/handle/2250/203903
Collections
The following license files are associated with this item: