A solution to Ringel’s circle problem

15.01.2025, 14:00 - 14:45  –  Campus Golm, Building 9, Room 2.22 and via Zoom
Institutskolloquium

Linda Kleist (Universität Potsdam)

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.

Afterwards around 2:45 pm: Tea and Coffee Break

Wenn Sie digital an dem Vortrag teilnehmen möchten, wenden Sie sich bitte an Christian Molle molle @ uni-potsdam.de, um die Zugangsdaten zu erhalten.