Coloraciones de algunas gráficas de fichas

Ponente(s): Omar Carbajal Bonal

Las gráficas de fichas (token graphs) descritas por Fabila-Monroy et al. (2009), para una gráfica G y un entero k ≥ 1, se define la gráfica de fichas Fk(G) como la gráfica cuyo conjunto de vértices esta conformado por todos los k−subconjuntos de V (G), donde dos vértices son adyacentes en Fk(G) siempre que la diferencia simétrica entre ambos subconjuntos sea un par de vértices adyacentes en G. Así, los vértices de Fk(G) corresponden a configuraciones de k fichas indistinguibles colocadas en distintos vértices de G, donde dos configuraciones son adyacentes siempre que se pueda alcanzar una configuración desde la otra moviendo una ficha a lo largo de una arista desde su posición actual hasta un vértice desocupado. Se mostraran algunos resultados sobre coloración de Fk(G), así como de algunas familias de gráficas