{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:38Z","timestamp":1740122378839,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T00:00:00Z","timestamp":1627862400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T00:00:00Z","timestamp":1627862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["613.009.127"],"award-info":[{"award-number":["613.009.127"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most <jats:italic>k<\/jats:italic>, when an effective divisor of degree <jats:italic>k<\/jats:italic> that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.<\/jats:p>","DOI":"10.1007\/s10878-021-00762-w","type":"journal-article","created":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T21:03:36Z","timestamp":1627938216000},"page":"2681-2699","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Constructing tree decompositions of graphs with bounded gonality"],"prefix":"10.1007","volume":"44","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Josse","family":"van Dobben de Bruyn","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0734-4511","authenticated-orcid":false,"given":"Dion","family":"Gijswijt","sequence":"additional","affiliation":[]},{"given":"Harry","family":"Smit","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,2]]},"reference":[{"issue":"6","key":"762_CR1","doi-asserted-by":"publisher","first-page":"613","DOI":"10.2140\/ant.2008.2.613","volume":"2","author":"M Baker","year":"2008","unstructured":"Baker M (2008) Specialization of linear systems from curves to graphs. Algebra Number Theory 2(6):613\u2013653","journal-title":"Algebra Number Theory"},{"issue":"2","key":"762_CR2","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1016\/j.aim.2007.04.012","volume":"215","author":"M Baker","year":"2007","unstructured":"Baker M, Norine S (2007) Riemann\u2013Roch and Abel\u2013Jacobi theory on a finite graph. Adv Math 215(2):766\u2013788","journal-title":"Adv Math"},{"key":"762_CR3","first-page":"2914","volume":"15","author":"M Baker","year":"2009","unstructured":"Baker M, Norine S (2009) Harmonic morphisms and hyperelliptic graphs. Int Math Res Not 15:2914\u20132955","journal-title":"Int Math Res Not"},{"key":"762_CR4","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.jcta.2012.07.011","volume":"120","author":"M Baker","year":"2013","unstructured":"Baker M, Shokrieh F (2013) Chip-firing games, potential theory on graphs, and spanning trees. J Comb Theory Ser B 120:164\u2013182","journal-title":"J Comb Theory Ser B"},{"key":"762_CR5","volume-title":"Nonserial dynamic programming","author":"U Bertele","year":"1972","unstructured":"Bertele U, Brioschi F (1972) Nonserial dynamic programming. Academic Press, New York"},{"issue":"1\u20132","key":"762_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender HL (1998) A partial k-arboretum of graphs with bounded treewidth. Theor Comput Sci 209(1\u20132):1\u201345. https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theor Comput Sci"},{"key":"762_CR7","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-3-030-58150-3_31","volume-title":"Computing and combinatorics","author":"HL Bodlaender","year":"2020","unstructured":"Bodlaender HL, van Dobben de Bruyn J, Gijswijt D, Smit H (2020) Constructing tree decompositions of graphs with bounded gonality. In: Kim D, Uma RN, Cai Z, Lee DH (eds) Computing and combinatorics. Springer, Cham, pp 384\u2013396"},{"issue":"2","key":"762_CR8","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1016\/j.aim.2012.02.019","volume":"230","author":"F Cools","year":"2012","unstructured":"Cools F, Draisma J, Payne S, Robeva E (2012) A tropical proof of the Brill\u2013Noether theorem. Adv Math 230(2):759\u2013776","journal-title":"Adv Math"},{"issue":"1\u20132","key":"762_CR9","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00208-014-1067-x","volume":"361","author":"G Cornelissen","year":"2015","unstructured":"Cornelissen G, Kato F, Kool J (2015) A combinatorial Li\u2013Yau inequality and rational points on curves. Mathematische Annalen 361(1\u20132):211\u2013258. https:\/\/doi.org\/10.1007\/s00208-014-1067-x","journal-title":"Mathematische Annalen"},{"issue":"1","key":"762_CR10","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle B (1990) The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform Comput 85(1):12\u201375. https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","journal-title":"Inform Comput"},{"key":"762_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"14","key":"762_CR12","doi-asserted-by":"publisher","first-page":"1613","DOI":"10.1103\/PhysRevLett.64.1613","volume":"64","author":"D Dhar","year":"1990","unstructured":"Dhar D (1990) Self-organized critical state of sandpile automaton models. Phys Rev Lett 64(14):1613","journal-title":"Phys Rev Lett"},{"key":"762_CR13","unstructured":"Dobben de Bruyn JV (2012) Reduced divisors and gonality in finite graphs. Bachelor thesis, Leiden University. https:\/\/www.universiteitleiden.nl\/binaries\/content\/assets\/science\/mi\/scripties\/bachvandobbendebruyn.pdf"},{"issue":"4","key":"762_CR14","doi-asserted-by":"publisher","first-page":"941","DOI":"10.5802\/alco.124","volume":"3","author":"J van Dobben de Bruyn","year":"2020","unstructured":"van Dobben de Bruyn J, Gijswijt D (2020) Treewidth is a lower bound on graph gonality. Algebr Combin 3(4):941\u2013953. https:\/\/doi.org\/10.5802\/alco.124","journal-title":"Algebr Combin"},{"key":"762_CR15","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.dam.2020.08.013","volume":"287","author":"D Gijswijt","year":"2020","unstructured":"Gijswijt D, Smit H, van der Wegen M (2020) Computing graph gonality is hard. Discrete Appl Math 287:134\u2013149","journal-title":"Discrete Appl Math"},{"issue":"2","key":"762_CR16","doi-asserted-by":"publisher","first-page":"1400","DOI":"10.1137\/16M1095329","volume":"32","author":"K Hendrey","year":"2018","unstructured":"Hendrey K (2018) Sparse graphs of high gonality. SIAM J Discrete Math 32(2):1400\u20131407","journal-title":"SIAM J Discrete Math"},{"key":"762_CR17","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson N, Seymour PD (1986) Graph minors. II. Algorithmic aspects of tree-width. J Algorithms 7:309\u2013322","journal-title":"J Algorithms"},{"key":"762_CR18","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"PD Seymour","year":"1993","unstructured":"Seymour PD, Thomas R (1993) Graph searching and a minimax theorem for tree-width. J Combin Theory Ser B 58:239\u2013257","journal-title":"J Combin Theory Ser B"},{"issue":"3","key":"762_CR19","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1017\/S0017089500030019","volume":"42","author":"H Urakawa","year":"2000","unstructured":"Urakawa H (2000) A discrete analogue of the harmonic morphism and Green kernel comparison theorems. Glasgow Math J 42(3):319\u2013334","journal-title":"Glasgow Math J"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00762-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00762-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00762-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:21:02Z","timestamp":1665778862000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00762-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,2]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["762"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00762-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,8,2]]},"assertion":[{"value":"26 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}