BARC talk by Linda Kleist

Wednesday, 25 May 2022, Linda Kleist, research scientist at Technische Universität Braunschweig, Department of Computer Science, Germany, will give a talk on "Ringel’s circle problem".

Title:
Ringel’s circle problem

Abstract:
In 1959, Ringel asked for the chromatic number of tangency graphs of a collection of circles in the plane in which no three circles have the same tangent point. Particularly, he wondered whether a finite number of colors always suffices. For the special case when the circles are not allowed to overlap, the four color theorem (in combination with Koebe’s disk packing theorem) asserts that four colors are always sufficient. 

When allowing overlaps, Ringel provided an example that 5 colors may be needed. Until recently, this was the best known lower bound.

In this talk, we construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. Hence, we provide a strong negative answer to Ringel's circle problem. The proof relies on a (multidimensional) version of Gallai’s theorem with polynomial constraints. The talk is based on joint work with James Davies, Chaya Keller, Shakhar Smorodinsky, and Bartosz Walczak.

Bio:
Linda Kleist is an academic staff member in the 'Algorithms' group of Sándor Fekete at TU Braunschweig, Germany. She obtained her PhD in 2018 at in the group 'Discrete Mathematics’ of Stefan Felsner and is interested in algorithmic oriented problems related to graphs and geometry. Linda visited Barc last spring/summer for 3 three months and is happy to be back for a short research visit.