@inproceedings{afc4b2a687024ecdbe494d35931156e3,
title = "A Solution to Ringel's Circle Problem",
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.",
keywords = "Gallai's theorem, chromatic number, circle arrangement, polynomial method",
author = "James Davies and Chaya Keller and Linda Kleist and Shakhar Smorodinsky and Bartosz Walczak",
note = "Publisher Copyright: {\textcopyright} James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak; licensed under Creative Commons License CC-BY 4.0; 38th International Symposium on Computational Geometry, SoCG 2022 ; Conference date: 07-06-2022 Through 10-06-2022",
year = "2022",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2022.33",
language = "אנגלית",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Xavier Goaoc and Michael Kerber",
booktitle = "38th International Symposium on Computational Geometry, SoCG 2022",
address = "גרמניה",
}