Coloración en grafos pigmentados

Abstract

En este trabajo se estudian problemas de coloración en grafos pigmentados. Un grafo pigmentado es una tupla $(G,c)$ con $G$ un grafo y $c:E(G)\to \NN$ una asignación de pigmentos en las aristas. El primer capítulo se centra en el problema de 1-coloración o bien realizabilidad, donde se busca la existencia de una asignación de pigmentos a los nodos, $f:V\to c(E)$, tal que $f(v)$ está en los pigmentos del corte (se dice que $f$ es realización) y en cada arista a lo más uno de sus extremos toma su pigmento ($f$ se dice buena). En particular se estudia la complejidad de este problema para grafos con uno a tres pigmentos, y en los casos $NP$-completo, para $G$ bipartito y para $G$ completo, y se dan algoritmos parametrizados para el caso general. Adicionalmente, se estudian variaciones del problema, como pedir que $f(v)$ tome valores en una lista dada $l_v$, que en cada arista al menos uno de los extremos tome su pigmento o pedir que $f$ solo sea buena en un subconjunto de las aristas. En el segundo capítulo se estudia la complejidad del problema de $k$-coloración, que consiste en una generalización de la bien realizabilidad, en el cual se busca la existencia de una partición de los vértices y una realización que es buena en cada parte. Finalmente, el capítulo tres se enfoca en dar una generalización del Teorema de Brooks para grafos pigmentados. En concreto se define $\chi(L)$ el número cromático, como el mínimo $k$ tal que un grafo pigmentado $L$ es $k$-coloreable. El objetivo es encontrar una cota calculable en tiempo polinomial para $\chi(L)$ y caracterizar aquellos grafos pigmentados que la alcanzan.