A solution to Ringel's circle problem

DOI10.4230/LIPICS.SOCG.2022.33MaRDI QIDQ6385228zbMATH OpenFDO

Authors James E. Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak

Publication date 9 December 2021

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2022.33

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 Ringel's circle problem (1959). The proof relies on a (multidimensional) version of Gallai's theorem with polynomial constraints, which we derive from the Hales-Jewett theorem and which may be of independent interest.

Cited in

(3)

• Discrete geometry. Abstracts from the workshop held January 21--26, 2024
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
• Prime and polynomial distances in colourings of the plane

This page was built for publication: A solution to Ringel's circle problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6385228)