Potencias y potencias exactas: Algoritmos y coloreos

Abstract

En esta tesis se trabaja con los siguientes conceptos de teoría de grafos: Dado un grafo $G$ y un entero positivo $p$, la potencia exacta $p$-ésima de $G$ denotada por $\exact{G}{p}$ es el grafo con el mismo conjunto de vértices de $G$; y entre dos vértices $u$ y $v$ hay una arista en $\exact{G}{p}$ si y solamente si los vértices $u$ y $v$ están a distancia \emph{exactamente} $p$ en $G$. Cuando $p=2$ se dice que $\exact{G}{2}$ es el cuadrado exacto de $G$ o que $G$ es una raíz cuadrada exacta de $\exact{G}{2}$. Y cuando $p=3$ se habla de cubos exactos y raíces cúbicas exactas respectivamente. Dado un grafo $G$ y un entero positivo $p$, la potencia $p$-ésima de $G$ denotada por $G^p$ es el grafo con el mismo conjunto de vértices de $G$; y entre dos vértices $u$ y $v$ hay una arista en $G^p$ si y solamente si los vértices $u$ y $v$ están a distancia a lo más $p$ en $G$. El \emph{número subcromático} de un grafo $G$, denotado por $\chi_{s}(G)$, es el menor número de colores necesarios para colorear los vértices del grafo, de manera que cada clase de color induce una unión disjunta de cliques. La noción clásica de número de coloreo se define como el menor entero $k$ tal que $G$ tiene un ordenamiento lineal de vértices en la que cada vértice tiene, a lo más, $k-1$ vecinos menores que él. Existen diversas generalizaciones de este concepto. En la primera parte de esta tesis se resuelve el problema de encontrar una caracterización para cuadrados exactos de árboles la cual conlleva a encontrar un algoritmo de reconocimiento que en tiempo polinomial determina si un grafo es el cuadrado exacto de un árbol. De igual manera se resuelve la caracterización, en dos de los tres casos posibles, para los cubos exactos de árboles obteniendo un esbozo de un algoritmo polinomial de reconocimiento. Y se resuelve el problema de encontrar una caracterización para los grafos que tienen raíces cuadradas exactas que son triangle-free. En la segunda parte se estudia el número subcromático de potencias de grafos, logrando mejorar la cota de dicho número para algunas familias de grafos poco densas. Para ello se introducen y estudian nuevos parámetros de números generalizados de coloreo.