De fichas y colores: Explorando las gráficas de fichas y sus coloraciones

Resumen:

En esta plática se presentará una visión general del estudio de las gráficas de fichas (token graphs), estructuras que han despertado un creciente interés por su rica combinatoria y sus conexiones con distintas áreas. Dado un grafo $G$ y un número natural $k$, la gráfica de fichas $F_k(G)$ tiene como vértices los subconjuntos de $k$ vértices de $G$, donde dos de ellos son adyacentes si su diferencia simétrica es un par de vértices adyacentes en $G$.
A partir de esta definición, exploramos propiedades básicas, algunos resultados conocidos sobre su espectro y estructura, y ejemplos que ilustran su comportamiento. También nos detendremos en las gráficas de Johnson, un caso particular de esta familia, donde discutiremos ideas relacionadas con las coloraciones completas y algunos avances preliminares.