Geodesic
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, Tome 3 (2020) no. 4, pp. 941-953.

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/alco.124
Classification : 05C57, 05C83, 14T05, 14H51
Mots-clés : 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
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@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://geodesic-test.mathdoc.fr/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://geodesic-test.mathdoc.fr/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://geodesic-test.mathdoc.fr/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, Tome 3 (2020) no. 4, pp. 941-953. doi : 10.5802/alco.124. https://geodesic-test.mathdoc.fr/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) | Zbl | MR | DOI

[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 | Zbl | MR | DOI

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

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

[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 | Zbl | MR | DOI

[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 | Zbl | MR | DOI

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

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

[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 | Zbl | MR | DOI

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

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

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

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

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

[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 | Zbl | MR | DOI

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

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

[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 | Zbl | MR | DOI

[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 | Zbl | MR | DOI

  • Morrison, Ralph; Speeter, Noah The gonality of queen's graphs, Discrete Mathematics, Volume 347 (2024) no. 12, p. 9 (Id/No 114186) | DOI:10.1016/j.disc.2024.114186 | Zbl:1547.05197
  • Dean, Frances; Everett, Max; Morrison, Ralph Multiplicity-free gonality on graphs, Electronic Journal of Graph Theory and Applications, Volume 11 (2023) no. 2, pp. 357-380 | DOI:10.5614/ejgta.2023.11.2.2 | Zbl:1538.05199
  • Metsch, Klaus On the treewidth of generalized Kneser graphs, The Australasian Journal of Combinatorics, Volume 86 (2023), pp. 477-486 | Zbl:1519.05212
  • Cenek, Lisa; Ferguson, Lizzie; Gebre, Eyobel; Marcussen, Cassandra; Meintjes, Jason; Morrison, Ralph; Ostermeyer, Liz; Ramakrishna, Shefali Uniform scrambles on graphs, The Australasian Journal of Combinatorics, Volume 87 (2023), pp. 129-147 | Zbl:1527.05106
  • Harp, Michael; Jackson, Elijah; Jensen, David; Speeter, Noah A new lower bound on graph gonality, Discrete Applied Mathematics, Volume 309 (2022), pp. 172-179 | DOI:10.1016/j.dam.2021.11.003 | Zbl:1480.05080
  • Echavarria, Marino; Everett, Max; Huang, Robin; Jacoby, Liza; Morrison, Ralph; Weber, Ben On the scramble number of graphs, Discrete Applied Mathematics, Volume 310 (2022), pp. 43-59 | DOI:10.1016/j.dam.2021.12.009 | Zbl:1482.05230
  • Bodlaender, Hans L.; Cornelissen, Gunther; van der Wegen, Marieke Problems hard for treewidth but easy for stable gonality, Graph-theoretic concepts in computer science. 48th international workshop, WG 2022, Tübingen, Germany, June 22–24, 2022. Revised selected papers, Cham: Springer, 2022, pp. 84-97 | DOI:10.1007/978-3-031-15914-5_7 | Zbl:7682403
  • Bodlaender, Hans L.; van Dobben de Bruyn, Josse; Gijswijt, Dion; Smit, Harry Constructing tree decompositions of graphs with bounded gonality, Journal of Combinatorial Optimization, Volume 44 (2022) no. 4, pp. 2681-2699 | DOI:10.1007/s10878-021-00762-w | Zbl:1505.05109
  • van Dobben de Bruyn, Josse; Smit, Harry; van der Wegen, Marieke Discrete and metric divisorial gonality can be different, Journal of Combinatorial Theory. Series A, Volume 189 (2022), p. 19 (Id/No 105619) | DOI:10.1016/j.jcta.2022.105619 | Zbl:1486.05201
  • Corey, Daniel Tropical curves of hyperelliptic type, Journal of Algebraic Combinatorics, Volume 53 (2021) no. 4, pp. 1215-1229 | DOI:10.1007/s10801-020-00959-y | Zbl:1465.14057
  • Bodlaender, Hans L.; van der Wegen, Marieke; van der Zanden, Tom C. Stable divisorial gonality is in NP, Theory of Computing Systems, Volume 65 (2021) no. 2, pp. 428-440 | DOI:10.1007/s00224-020-10019-4 | Zbl:1477.68204
  • Bodlaender, Hans L.; van Dobben de Bruyn, Josse; Gijswijt, Dion; Smit, Harry Constructing tree decompositions of graphs with bounded gonality, Computing and combinatorics. 26th international conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020. Proceedings, Cham: Springer, 2020, pp. 384-396 | DOI:10.1007/978-3-030-58150-3_31 | Zbl:7336120
  • Aidun, Ivan; Dean, Frances; Morrison, Ralph; Yu, Teresa; Yuan, Julie Treewidth and gonality of glued grid graphs, Discrete Applied Mathematics, Volume 279 (2020), pp. 1-11 | DOI:10.1016/j.dam.2019.10.024 | Zbl:1439.05164
  • Gijswijt, Dion; Smit, Harry; van der Wegen, Marieke Computing graph gonality is hard, Discrete Applied Mathematics, Volume 287 (2020), pp. 134-149 | DOI:10.1016/j.dam.2020.08.013 | Zbl:1450.05088
  • Bodewes, Jelco M.; Bodlaender, Hans L.; Cornelissen, Gunther; van der Wegen, Marieke Recognizing hyperelliptic graphs in polynomial time, Theoretical Computer Science, Volume 815 (2020), pp. 121-146 | DOI:10.1016/j.tcs.2020.02.013 | Zbl:1436.05105
  • Aidun, Ivan; Dean, Frances; Morrison, Ralph; Yu, Teresa; Yuan, Julie Graphs of gonality three, Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1197-1217 | DOI:10.5802/alco.80 | Zbl:1441.14203
  • Cools, Filip; Draisma, Jan On metric graphs with prescribed gonality, Journal of Combinatorial Theory. Series A, Volume 156 (2018), pp. 1-21 | DOI:10.1016/j.jcta.2017.11.017 | Zbl:1381.05012
  • Hujter, Bálint; Kiss, Viktor; Tóthmérész, Lilla On the complexity of the chip-firing reachability problem, Proceedings of the American Mathematical Society, Volume 145 (2017) no. 8, pp. 3343-3356 | DOI:10.1090/proc/13498 | Zbl:1365.05164

Cité par 18 documents. Sources : zbMATH