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

treewidthmetric graphgonalitytropical 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.

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

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• A Riemann-Roch theorem in tropical geometry
• A combinatorial Li-Yau inequality and rational points on curves
• 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
• 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

(22)

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

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)