Document Open Access Logo

Weak Coloring Numbers of Intersection Graphs

Authors Zdeněk Dvořák , Jakub Pekárek, Torsten Ueckerdt, Yelena Yuditsky

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2022.39.pdf
  • Filesize: 0.89 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Mathematics of computing → Graph coloring
Keywords
  • geometric intersection graphs
  • weak and strong coloring numbers

Metrics

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

Abstract

Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for a positive integer k, we seek a vertex ordering such that every vertex can (weakly respectively strongly) reach in k steps only few vertices that precede it in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in structural and algorithmic graph theory. Recently, Dvořák, McCarty, and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in ℝ^d, such as homothets of a compact convex object, or comparable axis-aligned boxes.
In this paper, we prove upper and lower bounds for the k-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in k, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).

Cite As Get BibTex

Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky. Weak Coloring Numbers of Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.39

Author Details

Zdeněk Dvořák
  • Charles University, Prague, Czech Republic
Jakub Pekárek
  • Charles University, Prague, Czech Republic
Torsten Ueckerdt
  • Karlsruhe Institute of Technology, Germany
Yelena Yuditsky
  • Université Libre de Bruxelles, Brussels, Belgium

Funding

  • Dvořák, Zdeněk: Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.
  • Pekárek, Jakub: Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.

Acknowledgements

This research was carried out at the workshop on Generalized Coloring Numbers organized by Michał Pilipczuk and Piotr Micek in February 2021. We would like to thank the organizers and all participants for creating a friendly and productive environment. Special thanks go to Stefan Felsner for fruitful discussions.

References

  1. Vida Dujmović, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. arXiv, 1907.05168, 2019. URL: http://arxiv.org/abs/1907.05168.
  2. Zdeněk Dvořák. Constant-factor approximation of domination number in sparse graphs. European Journal of Combinatorics, 34:833-840, 2013. Google Scholar
  3. Zdeněk Dvořák, Rose McCarty, and Sergey Norin. Sublinear separators in intersection graphs of convex shapes. SIAM Journal on Discrete Mathematics, 35(2):1149-1164, 2021. URL: https://doi.org/10.1137/20M1311156.
  4. Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On comparable box dimension. Manuscript. Google Scholar
  5. Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1-63:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.63.
  6. Louis Esperet and Jean-Florent Raymond. Polynomial expansion and sublinear separators. European Journal of Combinatorics, 69:49-53, 2018. Google Scholar
  7. Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. Coloring and covering nowhere dense graphs. SIAM Journal on Discrete Mathematics, 32:2467-2481, 2018. Google Scholar
  8. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 89-98. ACM, 2014. Google Scholar
  9. Gwenaël Joret and Piotr Micek. Improved bounds for weak coloring numbers. CoRR, 2021. URL: http://arxiv.org/abs/2102.10061.
  10. Hal A. Kierstead and Daqing Yang. Orderings on graphs and game coloring number. Order, 20(3):255-264, 2003. Google Scholar
  11. Paul Koebe. Kontaktprobleme der Konformen Abbildung. Math.-Phys. Kl., 88:141-164, 1936. Google Scholar
  12. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  13. Felix Reidl and Blair D. Sullivan. A color-avoiding approach to subgraph counting in bounded expansion classes. arXiv, 2001.05236, 2020. URL: http://arxiv.org/abs/2001.05236.
  14. Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. European Journal of Combinatorics, 66:129-144, 2017. Google Scholar
  15. Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete Math., 309(18):5562-5568, 2009. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact