Treewidth is a lower bound on graph gonality (Q2200865)

Let \(G = (V,E)\) be a finite and undirected graph. The treewidth of \(G\) is the minimum width of a tree decomposition of \(G\). The (divisorial) gonality of a \(G\) is the minimal width of a positive rank divisor on \(G\). (Several definitions for these terms exist, but the authors start with these in the paper.) As the title announces, the authors prove that the treewidth is a lower bound for the graph gonality. The distance between these parameters is traversed by means of brambles. A set \(\mathfrak{B} \subseteq 2^V - \{\emptyset\}\) is a bramble if for any \(B,B^\prime \in \mathfrak{B}\) the induced subgraph \(G[B \cup B^\prime]\) is connected. It's known that the treewidth of \(G\) is \(k\) if and only if \(G\) has a bramble of order at least \(k+1\). The relationship between the support of an effective divisor and the order of a bramble of order \(k+1\) is explored in order to derive the desired inequality. Note that several notions of graph gonality exist. The authors point out several such types and show that all satisfy the announced inequality.