- document
-
Bodlaender, Hans L. (author), van Dobben de Bruyn, J. (author), Gijswijt, Dion (author), Smit, Harry (author)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...journal article 2021
- document
-
Gijswijt, Dion (author), Smit, Harry J. (author), van der Wegen, Marieke (author)There are several notions of gonality for graphs. The divisorial gonality dgon(G) of a graph G is the smallest degree of a divisor of positive rank in the sense of Baker-Norine. The stable gonality sgon(G) of a graph G is the minimum degree of a finite harmonic morphism from a refinement of G to a tree, as defined by Cornelissen, Kato and Kool....journal article 2020
- document
-
Bodlaender, Hans L. (author), van Dobben de Bruyn, J. (author), Gijswijt, Dion (author), Smit, Harry (author)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...conference paper 2020