Graphs of Linear Growth have Bounded Treewidth

被引：0
作者：
Campbell, Rutger [1 ]
Distel, Marc [2 ]
Gollin, J. Pascal [1 ]
Harvey, Daniel J.
Hendrey, Kevin [1 ]
Hickingbotham, Robert [2 ]
Mohar, Bojan [3 ]
Wood, David R. [2 ]
机构：
[1] Inst Basic Sci IBS, Discrete Math Grp, Daejeon, South Korea
[2] Monash Univ, Sch Math, Melbourne, Australia
[3] Simon Fraser Univ, Dept Math, Burnaby, BC, Canada
来源：
ELECTRONIC JOURNAL OF COMBINATORICS | 2023年 / 30卷 / 03期
基金：
澳大利亚研究理事会; 加拿大自然科学与工程研究理事会;
关键词：
POLYNOMIAL-GROWTH; PLANAR GRAPHS; MINORS;
D O I：
10.37236/11657
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A graph class g has linear growth if, for each graph G E g and every positive integer r, every subgraph of G with radius at most r contains O(r) vertices. In this paper, we show that every graph class with linear growth has bounded treewidth.
引用
收藏
页数：12
相关论文
共 43 条
  • [1] Growth and percolation on the uniform infinite planar triangulation
    Angel, O
    [J]. GEOMETRIC AND FUNCTIONAL ANALYSIS, 2003, 13 (05) : 935 - 974
  • [2] [Anonymous], 1968, J. Diff. Geom.
  • [3] Bekos MA, 2020, J COMPUT GEOM, V11, P332
  • [4] The Book Thickness of 1-Planar Graphs is Constant
    Bekos, Michael A.
    Bruckdorfer, Till
    Kaufmann, Michael
    Raftopoulou, Chrysanthi N.
    [J]. ALGORITHMICA, 2017, 79 (02) : 444 - 465
  • [5] A partial k-arboretum of graphs with bounded treewidth
    Bodlaender, HL
    [J]. THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) : 1 - 45
  • [6] Linearity of grid minors in treewidth with applications through bidimensionality
    Demaine, Erik D.
    Hajiachayi, Mohammadtaghi
    [J]. COMBINATORICA, 2008, 28 (01) : 19 - 36
  • [7] Diestel R., 2017, Graduate Texts in Mathematics, V173, DOI [10.1007/978-3-662-53622-3, DOI 10.1007/978-3-662-53622-3]
  • [8] SOME RESULTS ON TREE DECOMPOSITION OF GRAPHS
    DING, G
    OPOROWSKI, B
    [J]. JOURNAL OF GRAPH THEORY, 1995, 20 (04) : 481 - 499
  • [9] Distel M, 2023, Arxiv, DOI arXiv:2210.12577
  • [10] Graph treewidth and geometric thickness parameters
    Dujmovic, Vida
    Wood, David R.
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2007, 37 (04) : 641 - 670
12345