Personal tools
You are here: Home CG seminar 2022 A Solution to Ringel’s Circle Problem
« August 2022 »
Log in

Forgot your password?

A Solution to Ringel’s Circle Problem

Wednesday, June 1st, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)


Chaya Keller, Ariel University


In 1959, Gerhard Ringel posed the following problem: What is the maximal number of colors needed for coloring any collection of circles, no three tangent at a point, such that any two tangent circles get different colors? 

The special case where the circles are non-overlapping was shown long ago to be equivalent to the celebrated 4-color theorem. The general case has remained open; it was only known that 4 colors are not sufficient. In this talk we show that no finite number of colors can suffice, by constructing collections of circles whose tangency graphs have an arbitrarily large girth (so in particular, no three are tangent at a point) and an arbitrarily large chromatic number. Our construction, which is one of the first geometric constructions of graphs with a large girth and a large chromatic number, relies on a (multidimensional) version of Gallai’s theorem with polynomial constraints, which may be of independent interest.

Joint work with James Davies, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak

Document Actions