Sobre grafos cubridores de los grafos de comparabilidad

Abstract

Un grafo es de comparabilidad si es posible orientar sus aristas en forma transitiva. Las primeras preguntas que surgen naturalmente son: el problema del reconocimiento, dado un grafo, ¿es de comparabilidad? Y si se tiene un grafo que es de comparabilidad, ¿cómo encontrar sus orientaciones transitivas? Brevemente, podría decirse que el presente trabajo se ocupa de problemas mucho más específicos: dado un grafo de comparabilidad, ¿existe una orientación que verifique una cierta propiedad dada? y en este contexto se estudian dos problemas. El primer problema tratado en este trabajo es saber cuáles grafos de comparabilidad admiten una orientación cuyo grafo cubridor es un árbol. A dicha clase de grafos la llamamos treelike. El otro problema tratado en el presente trabajo es, dado un conjunto de aristas fijo en un grafo de comparabilidad, ¿existe una orientación del grafo tal que su grafo cubridor contenga a dicho conjunto? Este problema, que en cierto modo generaliza al anterior, tiene además aplicaciones en problemas de programación de tareas.