Treewidth is a lower bound on graph gonality

DOI10.5802/ALCO.124zbMath1477.05125arXiv1407.7055OpenAlexW3081225756MaRDI QIDQ2200865

Josse van Dobben de Bruyn, Dion C. Gijswijt

Publication date: 23 September 2020

Published in: Algebraic Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

treewidthgonalitytropical curvemetric graph

Mathematics Subject Classification ID

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

Related Items (18)

Discrete and metric divisorial gonality can be different ⋮ Treewidth and gonality of glued grid graphs ⋮ Problems hard for treewidth but easy for stable gonality ⋮ Multiplicity-free gonality on graphs ⋮ On metric graphs with prescribed gonality ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing graph gonality is hard ⋮ Graphs of gonality three ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ Tropical curves of hyperelliptic type ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Stable divisorial gonality is in NP ⋮ The gonality of queen's graphs ⋮ A new lower bound on graph gonality ⋮ On the scramble number of graphs ⋮ On the complexity of the chip-firing reachability problem

Cites Work

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

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