Sparse graphs of high gonality

DOI10.1137/16M1095329MaRDI QIDQ4568093zbMATH OpenWikidataFDO

Authors Kevin Hendrey

Publication date 15 June 2018

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

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

zbMATH Keywords

treewidthdivisorial gonality

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42)

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).

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

Cites work

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

Cited in

(19)

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