2026-07-23T20:03:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16047 2024-03-06T10:56:49Z ddc:004 open_access

Weak Coloring Numbers of Intersection Graphs Dvořák, Zdeněk Pekárek, Jakub Ueckerdt, Torsten Yuditsky, Yelena geometric intersection graphs weak and strong coloring numbers 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zdeněk Dvořák and Jakub Pekárek and Torsten Ueckerdt and Yelena Yuditsky 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.39 urn:nbn:de:0030-drops-160477 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.39 eng https://creativecommons.org/licenses/by/4.0/legalcode