Treewidth is a lower bound on graph gonality

DOI10.5802/ALCO.124zbMATH Open1477.05125arXiv1407.7055OpenAlexW3081225756MaRDI QIDQ2200865FDOQ2200865

Authors: Josse van Dobben de Bruyn, Dion Gijswijt 

Publication date: 23 September 2020

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

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.

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

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

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)

Cites Work

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

Cited In (22)

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