Explorando problemas de coloraciones en gráficas y digráficas

Ponente(s): Diego Antonio Gonzalez Moreno

En ésta plática abordaremos problemas de coloraciones en gráficas. Recordemos, en teoría de las gráficas (o grafos), una coloración es una función que sujeta a ciertas restricciones asigna colores (o etiquetas), a elementos de una gráfica. En su forma más popular los elementos que se colorean son los vértices de una gráfica sujetos a que vértices adyacentes reciban colores distintos. También se han estudiado problemas en los cuales los elementos coloreados sean las aristas. Uno de los problemas de coloraciones que trataremos busca la existencia de estructuras heterocromáticas (o arcoíris) en gráficas coloreadas. El número anti-Ramsey, introducido Erdös y Simonovits en 1978 por Erdös y Simonovits, se define de la siguiente forma. Dadas dos gráficas $G$ y $H$, el número anti-Ramsey, al cual denotaremos por $ar(G, H)$, es el mínimo número de colores $k$ tal que toda coloración de las aristas de G con k colores, contiene una copia heterocromática (arcoíris) de $H$, es decir, una subgráfica isomorfa a $H$ en la cual todas las aristas de $H$ reciben color distinto. Tradicionalmente la gráfica $G$ es la gráfica completa y $H$ proviene de alguna familia de gráficas, por ejemplo, los ciclos, árboles o completas, entre otras. Debido a que en el problema clásico del número anti-Ramsey no se imponen condiciones sobre las coloraciones, una extensión natural de este problema consiste en agregar condiciones a las coloraciones. En esta plática abordaremos algunas restricciones que se pueden considerar en este problema. También hablaremos de otros problemas de coloraciones en gráficas y digráficas, sus orígenes y posibles aplicaciones.