UNAM

Coloreando jaulitas

Ponente: Mika Olsen
Institución: UAM-Cuajimalpa

Cuándo 12/11/2019
de 12:00 a 13:00
Dónde Auditorio "Alfonso Nápoles Gándara"
Agregar evento al calendario vCal
iCal

Cuentan que el estudio de coloraciones en teoría de las gráficas inició hace unos 200 años con el problema de los 4 colores. Hoy en día, las coloraciones son uno de los tópicos mas estudiados tanto por interés teórico como por la cantidad de aplicaciones que tienen y se estudian tanto coloraciones de vértices, coloraciones de aristas como coloraciones de vértices y artistas. Una coloración de los vértices de una gráfica induce una partición del conjunto de vértices en clases cromáticas. Una coloración es *propia* si no hay aristas entre vértices del mismo color, es decir, las clases cromáticas son conjuntos independientes.

El *número cromático* de una gráfica \(G\) es el mínimo número de colores de una coloración propia de \(G\).  El concepto de coloración propia se puede generalizar a otro tipo de coloraciones sólo cambiando las condiciones sobre las clases cromáticas. Estas generalizaciones a veces han sido impulsadas por interés teórico y a veces por alguna aplicación particular, o ambos. En esta plática voy a dar una breve  introducción al número cromático, sus aplicaciones y algunas de sus generalizaciones. Voy a revisar dos coloraciones que surgen de problemas que actualmente tienen mucho interés. El número cromático de empaquetamiento tiene aplicaciones en la asignación de radio frecuencias. Una coloración de los vértices de una gráfica es de *empaquetamiento* si los colores son números naturales y dos vértices del color \(i\) están a distancia mayor que \(i\). El *número cromático de empaquetamiento* es el mínimo número de colores de una coloración de empaquetamiento. 

Una coloración de las aristas de una gráfica es *arco iris* si entre cualquier para de vértices hay una trayectoria arco iris, es decir, una trayectoria cuyas aristas no repiten color. La *conexidad arco iris* se define como el mínimo número de colores de una coloración arco iris y  tiene aplicaciones en el área de seguridad cibernética.

Finalmente, voy a presentar resultados para la conexidad arco iris y para el número cromático de empaquetamiento de una \((k,g)\)-jaulita.

Las jaulas tienen propiedades estructurales que resultan convenientes en redes de comunicación y las jaulitas tienen propiedades estructurales heredadas de geometrías finitas.

archivado en: