Geodesic
Graphs of linear growth have bounded treewidth
Rutger Campbell1 ; Marc Distel2 ; J. Pascal Gollin1 ; Daniel J. Harvey ; Kevin Hendrey1 ; Robert Hickingbotham2 ; Bojan Mohar3 ; David Wood2
1Institute for Basic Science
2Monash University
3Simon Fraser University
The electronic journal of combinatorics, Tome 30 (2023) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A graph class $\mathcal{G}$ has linear growth if, for each graph $G \in \mathcal{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.
DOI : 10.37236/11657
Classification : 05C83, 05C62
Mots-clés : tree-decomposition of a graph, \(k\)-stack layout

Rutger Campbell  1   ; Marc Distel  2   ; J. Pascal Gollin  1   ; Daniel J. Harvey    ; Kevin Hendrey  1   ; Robert Hickingbotham  2   ; Bojan Mohar  3   ; David Wood  2

1 Institute for Basic Science
2 Monash University
3 Simon Fraser University 
@article{10_37236_11657,
     author = {Rutger Campbell and Marc Distel and J. Pascal Gollin and Daniel J. Harvey and Kevin Hendrey and Robert Hickingbotham and Bojan Mohar and David Wood},
     title = {Graphs of linear growth have bounded treewidth},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {3},
     doi = {10.37236/11657},
     zbl = {1519.05232},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11657/}
}
TY  - JOUR
AU  - Rutger Campbell
AU  - Marc Distel
AU  - J. Pascal Gollin
AU  - Daniel J. Harvey
AU  - Kevin Hendrey
AU  - Robert Hickingbotham
AU  - Bojan Mohar
AU  - David Wood
TI  - Graphs of linear growth have bounded treewidth
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11657/
DO  - 10.37236/11657
ID  - 10_37236_11657
ER  - 
%0 Journal Article
%A Rutger Campbell
%A Marc Distel
%A J. Pascal Gollin
%A Daniel J. Harvey
%A Kevin Hendrey
%A Robert Hickingbotham
%A Bojan Mohar
%A David Wood
%T Graphs of linear growth have bounded treewidth
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11657/
%R 10.37236/11657
%F 10_37236_11657
Rutger Campbell; Marc Distel; J. Pascal Gollin; Daniel J. Harvey; Kevin Hendrey; Robert Hickingbotham; Bojan Mohar; David Wood. Graphs of linear growth have bounded treewidth. The electronic journal of combinatorics, Tome 30 (2023) no. 3. doi: 10.37236/11657

Cité par Sources :