Personal tools
You are here: Home CG seminar 2022 A Solution to Ringel’s Circle Problem
« August 2022 »
August
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031
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)

underline

Chaya Keller, Ariel University

Abstract:

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