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 / El k-coloreo de vértices de un grafo es un ya conocido problema NP-completo, debido
a esto, los esfuerzos se han concentrado en estudiar el problema restringido a ciertas clases
de grafos, para intentar resolverlo en tiempo polinomial. Dentro de las clases de grafos más
estudiada, están los grafos H-free, que son los grafos que no poseen un grafo isomorfo a H
como subgrafo inducido.
En el presente trabajo se investigó el problema de 3-coloreo en las clases de grafos (P_{2d+3},C_{≤ 2d-1})-free (donde C_{≤2d−1} = {C_{2k+1} ∣ k ∈ N y k ≤ d}), para d ≥ 3, obteniendo los siguientes resultados:
Para el caso particular d = 3, se puede decidir si un grafo G de la clase ( P_9, C_5, C_3)-free
posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4).
Para todo d ≥ 3, se puede decidir si un grafo G de la clase (P_{2d+3},C_{≤ 2d-1}, C_8)-free posee
un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4).
Para todo d ≥ 3, se puede decidir si un grafo G de la clase ( P_{2d+3}, C_{≤2d−1})-free, que tiene
un ciclo C de largo 2d + 3 como subgrafo inducido, posee un 3-coloreo (y encontrarlo si
es que existe) en tiempo O(∣V (G)∣^4). / CMM - Conicyt PIA AFB170001
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/168091 |
| Date | January 2019 |
| Creators | Rojas Anríquez, Alberto Benjamín |
| Contributors | Stein, Maya, Soto San Martín, José, Matamala Vásquez, Martín |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0014 seconds