Número cromático y congruencias de ciclos

Ponente(s): Gerardo Miguel Tecpa Galván, Hortensia Galeana Sánchez

Calcular el número cromático en gráficas ha sido una tarea importante y retadora a lo largo de los años. Debido a su complejidad general, es natural el comparar al número cromático con otros parámetros y estructuras conocidas en gráficas, como los ciclos. En 1992, Tuza utilizó un árbol de búsqueda en profundidad para obtener coloraciones propias de gráficas mediante propiedades de las longitudes de los ciclos en la gráfica. En particular, demostró que una gráfica que no contiene ciclos de longitud congruente con 1 módulo k admite una k-coloración propia de sus vértices. En 2013, Diwan, Kenkre y Vishwanathan demostraron que si una gráfica tiene a lo más r ciclos de longitudes distintas pero congruentes con 1 módulo k, entonces G admite una coloración propia que utiliza rk+k colores. Por otro lado, en 2015, Chen, Ma, y Zang demostraron que, si una gráfica no contiene ciclos de longitud congruente con r módulo k, donde k≥r≥1, entonces χ(G)≤k si r es distinto de 2, y χ(G)≤k+1 en caso contrario. Siguiendo esta línea de investigación, en esta plática hablaremos sobre cómo las prohibiciones de algunos ciclos de ciertas longitudes permiten acotar el número cromático.