A solution to Ringel’s circle problem

by Prof. Linda Kleist (Universität Hamburg)

Tuesday 4 Nov 2025, 17:00 → 18:00 Europe/Berlin

H4 (Geomatikum)

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. For a long time, 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.