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

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.