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
DOI: https://doi.org/10.37236/11657

Abstract

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.

Published
2023-07-14
How to Cite
Campbell, R., Distel, M., Gollin, J. P., Harvey, D. J., Hendrey, K., Hickingbotham, R., Mohar, B., & Wood, D. (2023). Graphs of Linear Growth have Bounded Treewidth. The Electronic Journal of Combinatorics, 30(3), P3.1. https://doi.org/10.37236/11657
Issue
Volume 30, Issue 3 (2023)
Article Number
P3.1