Constructing tree decompositions of graphs with bounded gonality

Journal article (2021)

Authors

Hans L. Bodlaender Universiteit Utrecht
J. van Dobben de Bruyn Discrete Mathematics and Optimization - EEMCS
Dion Gijswijt Discrete Mathematics and Optimization - EEMCS
Harry Smit Max Planck Institute for Mathematics in the Sciences
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2021 Hans L. Bodlaender, J. van Dobben de Bruyn, Dion Gijswijt, Harry Smit
DOI: https://doi.org/10.1007/s10878-021-00762-w
Gonality Tree decomposition Chip firing
More Info
expand_more

Published Date

2021

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.