Constructing tree decompositions of graphs with bounded gonality
Hans L. Bodlaender (Universiteit Utrecht)
Josse van Dobben de Bruyn (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Dion Gijswijt (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Harry Smit (Universiteit Utrecht)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.