A Solution to Ringel’s Circle Problem

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



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.33.pdf
  • Filesize: 0.92 MB
  • 14 pages

Document Identifiers

Author Details

James Davies
  • University of Waterloo, Canada
Chaya Keller
  • Ariel University, Israel
Linda Kleist
  • Technische Universität Braunschweig, Germany
Shakhar Smorodinsky
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel
Bartosz Walczak
  • Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland

Acknowledgements

This work was initiated at the online workshop "Geometric graphs and hypergraphs". We thank the organizers Torsten Ueckerdt and Yelena Yuditsky for a very nice workshop and all participants for fun coffee breaks and a fruitful atmosphere.

Cite AsGet BibTex

James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak. A Solution to Ringel’s Circle Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.33

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • circle arrangement
  • chromatic number
  • Gallai’s theorem
  • polynomial method

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Kenneth Appel and Wolfgang Haken. Every planar map is four colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3):429-490, 1977. Google Scholar
  2. Kenneth Appel, Wolfgang Haken, and John Koch. Every planar map is four colorable. Part II: Reducibility. Illinois Journal of Mathematics, 21(3):491-567, 1977. Google Scholar
  3. Harold Scott Macdonald Coxeter. Introduction to geometry. John Wiley & Sons, 1961. Google Scholar
  4. James Davies. Box and segment intersection graphs with large girth and chromatic number. Advances in Combinatorics, 2021:7, 9 pp., 2021. URL: https://doi.org/10.19086/aic.25431.
  5. Aubrey D. N. J. de Grey. The chromatic number of the plane is at least 5. Geombinatorics, 28:5-18, 2018. Google Scholar
  6. Blanche Descartes. A three colour problem. Eureka, 9(21):24-25, 1947. Google Scholar
  7. Blanche Descartes. Solution to advanced problem no. 4526. The American Mathematical Monthly, 61:352, 1954. Google Scholar
  8. Hillel Furstenberg and Yitzhak Katznelson. A density version of the Hales-Jewett theorem. Journal d’Analyse Mathématique, 57:64-119, 1991. URL: https://doi.org/10.1007/BF03041066.
  9. Andrew W. Hales and Robert I. Jewett. Regularity and positional games. Transactions of the American Mathematical Society, 106(2):222-229, 1963. Google Scholar
  10. Brad Jackson and Gerhard Ringel. Colorings of circles. The American Mathematical Monthly, 91(1):42-49, 1984. URL: https://doi.org/10.1080/00029890.1984.11971333.
  11. Tommy R. Jensen and Bjarne Toft. Graph Coloring Problems. John Wiley & Sons, 1995. Google Scholar
  12. Gil Kalai. Some old and new problems in combinatorial geometry I: Around Borsuk’s problem. In Artur Czumaj, Agelos Georgakopoulos, Daniel Kráľ, Vadim Lozin, and Oleg Pikhurko, editors, Surveys in Combinatorics, volume 424 of London Mathematical Society Lecture Note Series, pages 147-174. Cambridge University Press, 2015. Google Scholar
  13. Paul Koebe. Kontaktprobleme der konformen Abbildung. Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse, 88:141-164, 1936. Google Scholar
  14. Alexandr V. Kostochka and Jaroslav Nešetřil. Properties of Descartes' construction of triangle-free graphs with high chromatic number. Combinatorics, Probability and Computing, 8(5):467-472, 1999. URL: https://doi.org/10.1017/S0963548399004022.
  15. János Pach. Finite point configurations. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, pages 26-50. CRC Press, 3rd edition, 2017. Google Scholar
  16. Hans Jürgen Prömel and Bernd Voigt. A sparse Graham-Rothschild theorem. Transactions of the American Mathematical Society, 309(1):113-137, 1988. URL: https://doi.org/10.1090/S0002-9947-1988-0957064-5.
  17. Hans Jürgen Prömel and Bernd Voigt. A sparse Gallai-Witt theorem. In Rainer Bodendiek and Rudolf Henn, editors, Topics in Combinatorics and Graph Theory, pages 747-755. Physica-Verlag Heidelberg, 1990. URL: https://doi.org/10.1007/978-3-642-46908-4_84.
  18. Richard Rado. Note on combinatorial analysis. Proceedings of the London Mathematical Society, 48:122-160, 1945. Google Scholar
  19. Gerhard Ringel. Färbungsprobleme auf Flächen und Graphen, volume 2 of Mathematische Monographien. VEB Deutscher Verlag der Wissenschaften, 1959. Google Scholar
  20. Alexander Soifer. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. Springer, 2009. Google Scholar
  21. Bartel L. van der Waerden. Beweis einer Baudetschen Vermutung. Nieuw Archief voor Wiskunde, 15:212-216, 1927. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail