3-coloreo en grafos con caminos y ciclos prohibidos

Abstract

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).