Informatics Colloquium 1.10. Old and new challenges in coloring graphs with geometric representation
Informatics Colloquium 1.10. 2019, 14:00 lecture hall D2
Bartosz Walczak, Department of Theoretical Computer Science, Jagiellonian
University, Kraków, Poland
Old and new challenges in coloring graphs with geometric representations
Abstract: A central problem in graph theory is to compute or estimate the
chromatic number of a graph, i.e., the minimum number of colors to be put on the
vertices so that no two neighbors receive the same color. Being very hard in
general, it has been considered for various restricted classes of graphs, in
which the chromatic number remains in a tighter connection to the structure of
the graph. This includes, in particular, classes of graphs defined on families
of geometric objects: intersection graphs, disjointness graphs, visibility
graphs, etc., motivated by various practical applications. In recent years, this
area of research has seen remarkable progress which has led to many classical
problems being solved and various new problems being raised. I will introduce
the audience to these old and new problems, present some of the recent
developments, and discuss connections to other areas, such as graph drawing and
approximation algorithms.