Defensa Tesis Licenciatura Pablo Terlisky
Título: Biclique-coloreo de grafos. Directores: Marina Groshaus y Francisco Soulignac
| Qué |
|
|---|---|
| Cuándo |
20/07/2010 de 03:00 pm a 04:00 pm |
| Dónde | Aula E24 |
| Agregar evento al calendario |
vCal
iCal
|
- Alumno: Pablo Terlisky
- Título: Biclique-coloreo de grafos
- Directores: Marina Groshaus y Francisco Soulignac
- Jurados: Pablo Factorovich y Min Chih Lin
- Resumen:
Un k-clique-coloreo de un grafo es una asignación de k colores a sus vértices de manera que toda clique tiene vértices con colores distintos. El problema de determinar si un grafo es k-clique coloreable es Sigma_2^p-Completo, aunque es más fácil para ciertas clases de grafos. En esta tesis, definimos el problema de k-biclique-coloreo como el análogo del de k-clique-coloreo en el contexto de bicliques. Probamos que el problema de determinar si un grafo es k-biclique-coloreable es Sigma_2^p-Completo para k > 1, y mostramos algunas clases de grafos para las que el problema está en NP o es polinomial.
