ALGEBRAIC COMBINATORICS

no. 4
Treewidth is a lower bound on graph gonality
van Dobben de Bruyn, Josse1; Gijswijt, Dion2
1 Mathematical Institute Leiden University P.O. Box 9512 2300 RA Leiden, The Netherlands
2 Delft Institute of Applied Mathematics Delft University of Technology Van Mourik Broekmanweg 6 2628 XE Delft, The Netherlands
Algebraic Combinatorics, Volume 3 (2020) no. 4, pp. 941-953.

We prove that the (divisorial) gonality of a finite connected graph is lower bounded by its treewidth. Graphs for which equality holds include the grid graphs and the complete multipartite graphs. We prove that the treewidth lower bound also holds for metric graphs (tropical curves) by constructing for any positive rank divisor on a metric graph a positive rank divisor of the same degree on a subdivision of the underlying combinatorial 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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.124
Classification: 05C57, 05C83, 14T05, 14H51
Keywords: Gonality, treewidth, tropical curve, metric graph.
van Dobben de Bruyn, Josse 1; Gijswijt, Dion 2

1 Mathematical Institute Leiden University P.O. Box 9512 2300 RA Leiden, The Netherlands
2 Delft Institute of Applied Mathematics Delft University of Technology Van Mourik Broekmanweg 6 2628 XE Delft, The Netherlands
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2020__3_4_941_0,
     author = {van Dobben de Bruyn, Josse and Gijswijt, Dion},
     title = {Treewidth is a lower bound on graph~gonality},
     journal = {Algebraic Combinatorics},
     pages = {941--953},
     publisher = {MathOA foundation},
     volume = {3},
     number = {4},
     year = {2020},
     doi = {10.5802/alco.124},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.124/}
}
TY  - JOUR
AU  - van Dobben de Bruyn, Josse
AU  - Gijswijt, Dion
TI  - Treewidth is a lower bound on graph gonality
JO  - Algebraic Combinatorics
PY  - 2020
SP  - 941
EP  - 953
VL  - 3
IS  - 4
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.124/
DO  - 10.5802/alco.124
LA  - en
ID  - ALCO_2020__3_4_941_0
ER  - 
%0 Journal Article
%A van Dobben de Bruyn, Josse
%A Gijswijt, Dion
%T Treewidth is a lower bound on graph gonality
%J Algebraic Combinatorics
%D 2020
%P 941-953
%V 3
%N 4
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.124/
%R 10.5802/alco.124
%G en
%F ALCO_2020__3_4_941_0
van Dobben de Bruyn, Josse; Gijswijt, Dion. Treewidth is a lower bound on graph gonality. Algebraic Combinatorics, Volume 3 (2020) no. 4, pp. 941-953. doi : 10.5802/alco.124. https://alco.centre-mersenne.org/articles/10.5802/alco.124/

[1] Baker, Matthew Specialization of linear systems from curves to graphs, Algebra Number Theory, Volume 2 (2008) no. 6, pp. 613-653 (With an appendix by Brian Conrad) | DOI | MR | Zbl

[2] Baker, Matthew; Norine, Serguei Riemann–Roch and Abel–Jacobi theory on a finite graph, Adv. Math., Volume 215 (2007) no. 2, pp. 766-788 | DOI | MR | Zbl

[3] Baker, Matthew; Norine, Serguei Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Not. IMRN (2009) no. 15, pp. 2914-2955 | DOI | MR | Zbl

[4] Biggs, Norman L. Chip-firing and the critical group of a graph, J. Algebraic Combin., Volume 9 (1999) no. 1, pp. 25-45 | DOI | MR | Zbl

[5] Björner, Anders; Lovász, László; Shor, Peter W. Chip-firing games on graphs, European J. Combin., Volume 12 (1991) no. 4, pp. 283-291 | DOI | MR | Zbl

[6] Caporaso, Lucia Gonality of algebraic curves and graphs, Algebraic and complex geometry (Springer Proc. Math. Stat.), Volume 71, Springer, Cham, 2014, pp. 77-108 | DOI | MR | Zbl

[7] Chan, Melody Tropical hyperelliptic curves, J. Algebraic Combin., Volume 37 (2013) no. 2, pp. 331-359 | DOI | MR | Zbl

[8] Chandran, L. Sunil; Kavitha, Telikepalli The treewidth and pathwidth of hypercubes, Discrete Math., Volume 306 (2006) no. 3, pp. 359-365 | DOI | MR | Zbl

[9] Cornelissen, Gunther; Kato, Fumiharu; Kool, Janne A combinatorial Li–Yau inequality and rational points on curves, Math. Ann., Volume 361 (2015) no. 1-2, pp. 211-258 | DOI | MR | Zbl

[10] Diestel, Reinhard Graph theory, Graduate Texts in Mathematics, 173, Springer, Heidelberg, 2012, xviii+436 pages | DOI | MR | Zbl

[11] van Dobben de Bruyn, Josse Reduced divisors and gonality in finite graphs, Bachelor thesis, Leiden University (2012) https://www.math.leidenuniv.nl/scripties/BachvanDobbendeBruyn.pdf

[12] Gathmann, Andreas; Kerber, Michael A Riemann–Roch theorem in tropical geometry, Math. Z., Volume 259 (2008) no. 1, pp. 217-230 | DOI | MR | Zbl

[13] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | DOI | MR | Zbl

[14] Halin, Rudolf S-functions for graphs, J. Geom., Volume 8 (1976) no. 1-2, pp. 171-186 | DOI | MR | Zbl

[15] Hladký, Jan; Král’, Daniel; Norine, Serguei Rank of divisors on tropical curves, J. Combin. Theory Ser. A, Volume 120 (2013) no. 7, pp. 1521-1538 | DOI | MR | Zbl

[16] Luo, Ye Rank-determining sets of metric graphs, J. Combin. Theory Ser. A, Volume 118 (2011) no. 6, pp. 1775-1793 | DOI | MR | Zbl

[17] Merino, Criel The chip-firing game, Discrete Math., Volume 302 (2005) no. 1-3, pp. 188-210 | DOI | MR | Zbl

[18] Robertson, Neil; Seymour, Paul D. Graph minors. IV. Tree-width and well-quasi-ordering, J. Combin. Theory Ser. B, Volume 48 (1990) no. 2, pp. 227-254 | DOI | MR | Zbl

[19] Seymour, Paul D.; Thomas, Robin Graph searching and a min-max theorem for tree-width, J. Combin. Theory Ser. B, Volume 58 (1993) no. 1, pp. 22-33 | DOI | MR | Zbl

Cited by Sources: