Coloraciones completas en gráficas planas

Autor: Fernando Esteban Contreras Mendoza
Coautor(es): M. Gabriela Araujo-Pardo, F. Esteban Contreras-Mendoza, Sara J. Murillo-García, Andrea B. Ramos-Tort, Christian Rubio-Montiel
Existen diversas condiciones sobre las posibles coloraciones de los vertices de una gráfica en las que uno puede pensar. Una de ellas, seguramente más conocida, es la condición de que a cualesquiera dos vértices adyacentes les sean asignados colores distintos (coloraciones propias), mientras que una condición ligeramente menos conocida, es la condición de que dada un paleta de colores, cualquier par de colores distintos de dicha paleta, se puedan encontrar como extremos de una arista en la gráfica (coloraciones completas). En esta charla hablaremos de cotas asintoticamente justas referentes a la cantidad de colores con la que se pueden realizar coloraciones completas y coloraciones que son propias y completas a la vez, lo anterior en el caso de las gráficas planas y otras gráficas relacionadas a ellas.