Colloquium Details
Graph homomorphisms and Frequency Assignment
| Author: | Jan Kratochvil Charles University, Prague, CZ |
|---|---|
| Date: | January 17, 2006 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
The notion of distance constrained graph labeling is motivated by the highly applied Frequency Assignment Problem. At the same time it proves to be a source of very interesting questions and results from the theoretical point of view. I will introduce the problem including the motivation from FAP, show the connection to the algebraic notion of graph homomorphisms and present an overview of recent results in this area of Graph Theory. These will include new upper bounds in terms of maximum degree, computational complexity for graphs of bounded tree-width and a relationship to the constrained Satisfaction Problem.
Biography
Jan Kratochvil is a professor of computer science and head of the Department of Applied Mathematics at Charles University in Prague, Czech Republic. He received his Ph.D. in 1987 at Charles University and since then has worked in Graph Theory. His research interests include computational complexity, graph coloring problems and geometric representations of graphs. He visited UO as a Fulbright fellow in 1994 and lectured here as a visiting associate professor in spring of 1995 and fall of 1999. He has published over 80 research papers in international journals and refereed proceedings of computer science conferences, many of them jointly with A. Proskurowski. Jan Kratochvil is currently the president of the Czech Mathematical Society.