Treewidth is a lower bound on graph gonality

J van Dobben de Bruyn, D.C. Gijswijt

Research output: Contribution to journalArticleScientificpeer-review

1 Downloads (Pure)

Abstract

We prove that the (divisorial) gonality of a finite connected graph is lower bounded by its treewidth. We show that equality holds for grid graphs and complete multipartite graphs. We prove that the treewidth lower bound also holds for metric graphs by constructing for any positive rank divisor on a metric graph Γ a positive rank divisor of the same degree on a subdivision of the underlying graph. Finally, we show that the treewidth lower bound also holds for a related notion of gonality defined by Caporaso and for stable gonality as introduced by Cornelissen et al.
Original languageEnglish
Pages (from-to)941-963
Number of pages10
JournalAlgebraic Combinatorics
Volume3
Issue number4
DOIs
Publication statusPublished - 2020

Fingerprint Dive into the research topics of 'Treewidth is a lower bound on graph gonality'. Together they form a unique fingerprint.

Cite this