## Combinatorics Seminar - Spring
'22

When: Sunday, March 27,
10am

Where: 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

##