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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יוני 2022
אירוע38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, גרמניה
משך הזמן: 7 יוני 202210 יוני 2022

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך224
ISSN (מודפס)1868-8969

כנס

כנס38th International Symposium on Computational Geometry, SoCG 2022
מדינה/אזורגרמניה
עירBerlin
תקופה7/06/2210/06/22

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A Solution to Ringel's Circle Problem'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי