LIPIcs.SoCG.2022.39.pdf
- Filesize: 0.89 MB
- 15 pages
Document
Weak Coloring Numbers of Intersection Graphs
Authors
Zdeněk Dvořák 
,
Yelena Yuditsky
-
Part of:
Volume:
38th International Symposium on Computational Geometry (SoCG 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-01
File
Document Identifiers
Author Details
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.
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
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).
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)
0PDF Downloads
References
- 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.
-
Zdeněk Dvořák. Constant-factor approximation of domination number in sparse graphs. European Journal of Combinatorics, 34:833-840, 2013.
- 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.
-
Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On comparable box dimension. Manuscript.
- 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.
-
Louis Esperet and Jean-Florent Raymond. Polynomial expansion and sublinear separators. European Journal of Combinatorics, 69:49-53, 2018.
-
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.
-
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.
- Gwenaël Joret and Piotr Micek. Improved bounds for weak coloring numbers. CoRR, 2021. URL: http://arxiv.org/abs/2102.10061.
-
Hal A. Kierstead and Daqing Yang. Orderings on graphs and game coloring number. Order, 20(3):255-264, 2003.
-
Paul Koebe. Kontaktprobleme der Konformen Abbildung. Math.-Phys. Kl., 88:141-164, 1936.
-
Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics. Springer, 2012.
- 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.
-
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.
-
Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete Math., 309(18):5562-5568, 2009.