Constructing tree decompositions of graphs with bounded gonality

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Downloads (Pure)

Abstract

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
Pages (from-to)2681-2699
Number of pages19
JournalJournal of Combinatorial Optimization
Volume44
Issue number4
DOIs
Publication statusPublished - 2021

Keywords

  • Chip firing
  • Gonality
  • Tree decomposition

Fingerprint

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

Cite this