Asymptotic dimension of intersection graphs

被引:0
|
作者
Dvorak, Zdenek [1 ]
Norin, Sergey [2 ]
机构
[1] Charles Univ Prague, Prague, Czech Republic
[2] McGill Univ, Montreal, PQ, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
D O I
10.1016/j.ejc.2022.103631
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We show that intersection graphs of compact convex sets in R(n )of bounded aspect ratio have asymptotic dimension at most 2n+ 1. More generally, we show this is the case for intersection graphs of systems of subsets of any metric space of Assouad- Nagata dimension n that satisfy the following condition: For each r, s > 0 and every point p, the number of pairwise-disjoint elements of diameter at least s in the system that are at distance at most r from p is bounded by a function of r/s. (c) 2022 Elsevier Ltd. All rights reserved.
引用
收藏
页数:10
相关论文
共 50 条
  • [21] Chordal graphs as intersection graphs of pseudosegments
    Dangelmayr, Cornelia
    Felsner, Stefan
    GRAPH DRAWING, 2007, 4372 : 208 - +
  • [22] COMPARABILITY-GRAPHS AND INTERSECTION GRAPHS
    GOLUMBIC, MC
    ROTEM, D
    URRUTIA, J
    DISCRETE MATHEMATICS, 1983, 43 (01) : 37 - 46
  • [23] Intersection graphs of pseudosegments: Chordal graphs
    Dangelmayr C.
    Felsner S.
    Trotter W.T.
    Journal of Graph Algorithms and Applications, 2010, 14 (02) : 199 - 220
  • [24] INTERSECTION GRAPHS OF R-GRAPHS
    GARDNER, ML
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 23 (07): : A655 - A655
  • [25] Subspace intersection graphs
    Laison, Joshua D.
    Qing, Yulan
    DISCRETE MATHEMATICS, 2010, 310 (23) : 3413 - 3416
  • [26] INTERSECTION THEORY FOR GRAPHS
    BRYLAWSKI, T
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 30 (02) : 233 - 246
  • [27] Modular intersection graphs
    McMorris, FR
    Wang, C
    GRAPHS AND COMBINATORICS, 1996, 12 (03) : 267 - 281
  • [28] INTERSECTION OF RANDOM GRAPHS
    KLIMOV, GP
    HARRISON, W
    DOKLADY AKADEMII NAUK SSSR, 1988, 302 (04): : 799 - 802
  • [29] Signed intersection graphs
    Acharya, B. D.
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2010, 13 (06): : 553 - 569
  • [30] ON GRID INTERSECTION GRAPHS
    HARTMAN, IBA
    NEWMAN, I
    ZIV, R
    DISCRETE MATHEMATICS, 1991, 87 (01) : 41 - 52