Treewidth is a lower bound on graph gonality
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: 2019-09-12
Revised: 2020-04-11
Accepted: 2020-04-12
Published online: 2020-08-20
DOI: https://doi.org/10.5802/alco.124
Classification: 05C57,  05C83,  14T05,  14H51
Keywords: Gonality, treewidth, tropical curve, metric graph.
@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},
     publisher = {MathOA foundation},
     volume = {3},
     number = {4},
     year = {2020},
     pages = {941-953},
     doi = {10.5802/alco.124},
     language = {en},
     url = {alco.centre-mersenne.org/item/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/item/ALCO_2020__3_4_941_0/

[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) | Article | MR 2448666 | Zbl 1162.14018

[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 | Article | MR 2355607 | Zbl 1124.05049

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

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

[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 | Article | MR 1120415 | Zbl 0729.05048

[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 | Article | MR 3278571 | Zbl 1395.14026

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

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

[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 | Article | MR 3302619 | Zbl 1341.11034

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

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

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

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

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

[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 | Article | MR 3092681 | Zbl 1317.14137

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

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

[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 | Article | MR 1046757 | Zbl 0719.05032

[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 | Article | MR 1214888 | Zbl 0795.05110