Graphs of Linear Growth have Bounded Treewidth

Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

Abstract

A graph class G has linear growth if, for each graph G ∈ 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. Mathematics Subject Classifications: 05C83, 05C62.

Original languageEnglish
Article numberP3.1
Number of pages12
JournalElectronic Journal of Combinatorics
Volume30
Issue number3
DOIs
Publication statusPublished - 14 Jul 2023

Cite this