[Todos] Seminario de Optimización y Grafos este jueves

[Flavia Bonomo]

Invitamos a todos al Seminario de Optimización y Grafos, edición 2008, del
grupo de investigación en Teoría de Grafos y Optimización Combinatoria
(http://www.dc.uba.ar/inv/grupos/grafos)
de los departamentos de Computación y Matemática de la FCEN, UBA y el
Instituto de Ciencias de la UNGS.

El seminario es los jueves de 19 a 20.30, y el cronograma preliminar
puede verse en http://www.dc.uba.ar/inv/grupos/grafos/seminario

Los invitamos este jueves 4 de diciembre a la próxima charla, desde las
19hs en el Laboratorio 3 (planta baja, pab I).

--------
"Sobre el problema de elegibilidad en el coloreo de grafos"

Ivo Koch (DC, FCEN, UBA)
--------

Resumen de la charla:

El problema de choosability fue planteado a mediados de los '70 por Erdös,
Rubin y Taylor. Se trata de una generalización del problema de coloreo de
grafos y consiste en asociar a cada vértice de un grafo G una lista de
colores admisibles del mismo tamaño k. Se busca encontrar el mínimo k tal
que cualquier coloreo de G, eligiendo para cada vértice un color de su
lista, sea un coloreo válido de G. Este k se llama choice number de G,
ch(G). En este problema es de gran interés conocer los casos en que el
choice number es igual al número cromático de G. Uno las conjeturas más
importantes en esta área es comprobar si ch(L(G)) = X(L(G)) para G, si G
es un multigrafo y L(G) su grafo de línea. X(G) es el número cromático de
G. Adicionalmente, Alon conjeturó en 1995 que si G es la unión
eje-disjunta de n grafos de orden n cada uno, entonces ch(G) = n. Se
mostrarán las direcciones de trabajo actuales en ambos problemas.