Sparse graphs of high gonality

DOI10.1137/16M1095329zbMATH Open1388.05105arXiv1606.06412WikidataQ129696347 ScholiaQ129696347MaRDI QIDQ4568093FDOQ4568093

Authors: Kevin Hendrey 

Publication date: 15 June 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: By considering graphs as discrete analogues of Riemann surfaces, Baker and Norine (Adv. Math. 2007) developed a concept of linear systems of divisors for graphs. Building on this idea, a concept of gonality for graphs has been defined and has generated much recent interest. We show that there are connected graphs of treewidth 2 of arbitrarily high gonality. We also show that there exist pairs of connected graphs $G,H$ such that $HsubseteqG$ and $H$ has strictly lower gonality than $G$. These results resolve three open problems posed in a recent survey by Norine (Surveys in Combinatorics 2015).

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

Recommendations

• Treewidth is a lower bound on graph gonality
• scientific article; zbMATH DE number 7301092
• Gonality sequences of graphs
• Constructing tree decompositions of graphs with bounded gonality
• On the gonality of graphs and connections to orientable genus

zbMATH Keywords

treewidthdivisorial gonality

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42)

Cites Work

• Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
• Riemann-Roch for sub-lattices of the root lattice \(A_n\)
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Title not available (Why is that?)
• A partial k-arboretum of graphs with bounded treewidth
• Algebraic and combinatorial rank of divisors on finite graphs
• Riemann-Roch theory for weighted graphs and tropical curves
• A tropical proof of the Brill-Noether theorem
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• On metric graphs with prescribed gonality
• Gonality of random graphs
• A Spectral Lower Bound for the Divisorial Gonality of Metric Graphs
• A Riemann-Roch theorem for edge-weighted graphs
• New tools and results in graph minor structure theory

Cited In (19)

• Constructing tree decompositions of graphs with bounded gonality
• On the gonality of Cartesian products of graphs
• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• On the gonality of graphs and connections to orientable genus
• On the semigroup of graph gonality sequences
• Computing graph gonality is hard
• Homomorphisms from sparse graphs with large girth.
• Gonality sequences of graphs
• Multiplicity-free gonality on graphs
• A new lower bound on graph gonality
• Sparse halves in dense triangle-free graphs
• Gonality of random graphs
• Treewidth and gonality of glued grid graphs
• Brill-Noether conjecture on cactus graphs
• Structural Properties of Sparse Graphs
• Recognizing hyperelliptic graphs in polynomial time
• Sparse hypergraphs with low independence number
• Constructing tree decompositions of graphs with bounded gonality
• Treewidth is a lower bound on graph gonality

This page was built for publication: Sparse graphs of high gonality

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