Talk information

Date: Sunday, March 27, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Shakhar Smorodinsky (Ben Gurion University)
Title: A Solution to Ringel's Circle Problem

Abstract:

Suppose we are given a finite family $\mathcal{C}$ of circles in the plane. The circles in $\mathcal{C}$ may overlap (i.e., two circles have two points in common) or be tangent (only one point in common) but no three circles may be pairwise tangent at the same point. Consider the tangency graph $G(\mathcal{C})$ on $\mathcal{C}$ where two circles form an edge if and only if they are tangent. In 1959 Gerhard Ringel asked whether the chromatic number of the tangency graph $G(\mathcal{C})$ is bounded? He also showed that it is at least $5$. We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to that problem.

Joint work with James Davis, Chaya Keller, Linda Kleist and Bartosz Walczak