Treewidth is a lower bound on graph gonality

DOI10.5802/ALCO.124MaRDI QIDQ2200865zbMATH OpenOpenAlexFDO

Authors Josse van Dobben de Bruyn, Dion Gijswijt

Publication date 23 September 2020

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1407.7055

zbMATH Keywords

gonalitymetric graphtreewidthtropical curve

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph minors (05C83) Special divisors on curves (gonality, Brill-Noether theory) (14H51) Tropical geometry (14T99)

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 emph{metric graphs} by constructing for any positive rank divisor on a metric graph $Gamma$ 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.

Review text

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.

Recommendations

• Constructing tree decompositions of graphs with bounded gonality
• Treewidth and gonality of glued grid graphs
• Sparse graphs of high gonality
• A new lower bound on graph gonality
• A Spectral Lower Bound for the Divisorial Gonality of Metric Graphs

Cites work

• A combinatorial Li-Yau inequality and rational points on curves
• A Riemann-Roch theorem in tropical geometry
• Chip-firing and the critical group of a graph
• Chip-firing games on graphs
• Gonality of algebraic curves and graphs
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph searching and a min-max theorem for tree-width
• Graph theory
• Harmonic Morphisms and Hyperelliptic Graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• Rank of divisors on tropical curves
• Rank-determining sets of metric graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• S-functions for graphs
• Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
• The chip-firing game
• The treewidth and pathwidth of hypercubes
• Tropical hyperelliptic curves

Cited in

(26)

• On metric graphs with prescribed gonality
• Computing graph gonality is hard
• Tropical curves of hyperelliptic type
• A new lower bound on graph gonality
• On the scramble number of graphs
• Discrete and metric divisorial gonality can be different
• Treewidth and gonality of glued grid graphs
• On the gonality of Cartesian products of graphs
• Graphs of gonality three
• Sparse graphs of high gonality
• Gonality sequences of graphs
• On the complexity of the chip-firing reachability problem
• A managed Bayesian risk approach for decision making alternatives
• Constructing tree decompositions of graphs with bounded gonality
• Stable divisorial gonality is in NP
• Constructing tree decompositions of graphs with bounded gonality
• Recognizing hyperelliptic graphs in polynomial time
• Problems hard for treewidth but easy for stable gonality
• Uniform scrambles on graphs
• Multiplicity-free gonality on graphs
• scientific article; zbMATH DE number 7731184 (Why is no real title available?)
• The gonality of queen's graphs
• On the treewidth of generalized q-Kneser graphs
• Divisorial and geometric gonality of higher-rank tropical curves
• Fibonacci sumsets and the gonality of strip graphs
• Scramble number and tree-cut decompositions

This page was built for publication: Treewidth is a lower bound on graph gonality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200865)