A Solution to Ringel's Circle Problem

James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

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.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف38th International Symposium on Computational Geometry, SoCG 2022
المحررونXavier Goaoc, Michael Kerber
ناشرSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
رقم المعيار الدولي للكتب (الإلكتروني)9783959772273
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يونيو 2022
الحدث38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, ألمانيا
المدة: ٧ يونيو ٢٠٢٢١٠ يونيو ٢٠٢٢

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت224
رقم المعيار الدولي للدوريات (المطبوع)1868-8969

!!Conference

!!Conference38th International Symposium on Computational Geometry, SoCG 2022
الدولة/الإقليمألمانيا
المدينةBerlin
المدة٧/٠٦/٢٢١٠/٠٦/٢٢

بصمة

أدرس بدقة موضوعات البحث “A Solution to Ringel's Circle Problem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا