Constructing tree decompositions of graphs with bounded gonality

Hans L. Bodlaender, Josse van Dobben de Bruyn, Dion Gijswijt, Harry Smit

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
24 Downloads (Pure)


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 k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.

Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication26th International Conference, COCOON 2020, Proceedings
EditorsDonghyun Kim, R.N. Uma, Zhipeng Cai, Dong Hoon Lee
Place of PublicationCham
PublisherSpringer Science+Business Media
Number of pages13
ISBN (Electronic)978-3-030-58150-3
ISBN (Print)978-3-030-58149-7
Publication statusPublished - 2020
Event26th International Conference on Computing and Combinatorics, COCOON 2020 - Atlanta, United States
Duration: 29 Aug 202031 Aug 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference26th International Conference on Computing and Combinatorics, COCOON 2020
Country/TerritoryUnited States

Bibliographical note

Accepted author manuscript


Dive into the research topics of 'Constructing tree decompositions of graphs with bounded gonality'. Together they form a unique fingerprint.

Cite this